結果
問題 | No.678 2Dシューティングゲームの必殺ビーム |
ユーザー |
![]() |
提出日時 | 2018-04-27 23:06:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 4,622 bytes |
コンパイル時間 | 1,592 ms |
コンパイル使用メモリ | 128,900 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-06-27 22:11:34 |
合計ジャッジ時間 | 2,322 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
# include <iostream># include <algorithm>#include <array># include <cassert>#include <cctype>#include <climits>#include <numeric># include <vector># include <string># include <set># include <map># include <cmath># include <iomanip># include <functional># include <tuple># include <utility># include <stack># include <queue># include <list># include <bitset># include <complex># include <chrono># include <random># include <limits.h># include <unordered_map># include <unordered_set># include <deque># include <cstdio># include <cstring>#include <stdio.h>#include <stdlib.h>#include <cstdint>#include <cfenv>//#include <bits/stdc++.h>using namespace std;using LL = long long;using ULL = unsigned long long;long long MOD = 1000000000 + 7;constexpr long long INF = std::numeric_limits<LL>::max();const double PI = acos(-1);#define fir first#define sec second#define thi third#define debug(x) cerr<<#x<<": "<<x<<'\n'typedef pair<LL, LL> Pll;typedef pair<LL, pair<LL, LL>> Ppll;typedef pair<LL, pair<LL, bitset<100001>>> Pbll;typedef pair<LL, pair<LL, vector<LL>>> Pvll;typedef pair<LL, LL> Vec2;struct Tll { LL first, second, third; };typedef pair<LL, Tll> Ptll;#define rep(i,rept) for(LL i=0;i<rept;i++)#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)LL h, w, n, m, k, s, t, q, last, cnt, sum, ans, d[400000];string str, ss;bool f[100000];char c;int di[4][2] = { { 0,1 },{ 1,0 },{ -1,0 } ,{ 0,-1 } };struct Edge { LL to, cost; };vector<Edge>vec[200000];void YN(bool f) {if (f)cout << "YES" << endl;elsecout << "NO" << endl;}void yn(bool f) {if (f)cout << "Yes" << endl;elsecout << "No" << endl;}struct ene {LL fi,se, th, fo,ff;};ene a[100000];struct Seg {LL n;vector<LL>node, lazy;Seg(vector<LL>v) {n = 1; while (n < v.size())n *= 2;node.resize(n * 2 - 1);lazy.resize(n * 2 - 1);rep(i, n)node[n + i - 1] = v[i];Mfor(i, n - 2)node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);//rep(i, n * 2 - 1)lazy[i] = -1;}Seg(LL n_) {n = 1; while (n < n_)n *= 2;node.resize(n * 2 - 1);lazy.resize(n * 2 - 1);rep(i, n)node[n + i - 1] = 1000000;Mfor(i, n - 2)node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);//区間最小などの時rep(i, n * 2 - 1)lazy[i] = -1;}//区間の和の遅延void eval(LL k, LL l, LL r) {if (lazy[k] != 0) {node[k] += lazy[k];if (r - l >= 1) {lazy[k * 2 + 1] += lazy[k] / 2;lazy[k * 2 + 2] += lazy[k] / 2;}lazy[k] = 0;}}//区間の最小の遅延void ceval(LL k, LL l, LL r) {if (lazy[k] != -1) {node[k] = lazy[k];if (r - l >= 1) {lazy[k * 2 + 1] = lazy[k];lazy[k * 2 + 2] = lazy[k];}lazy[k] = -1;}}void update(LL i, LL x) {i = i + n - 1;node[i] = x;while (i > 0) {i = (i - 1) / 2;node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);}}void update(LL i, LL x, LL a, LL b, LL l, LL r) {ceval(i, a, b);if (b < l || r < a)return;if (l <= a&&b <= r) {lazy[i] = x;ceval(i, a, b);}else {update(i * 2 + 1, x, a, (a + b) / 2, l, r);update(i * 2 + 2, x, (a + b + 1) / 2, b, l, r);node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);}}LL find(LL i, LL a, LL b, LL l, LL r) {ceval(i, a, b);if (b< l || r < a)return INF;if (l <= a&&b <= r)return node[i];return min(find(i * 2 + 1, a, (a + b) / 2, l, r), find(i * 2 + 2, (a + b + 1) / 2, b, l, r));}void add(LL i, LL x) {i = i + n - 1;node[i] += x;while (i > 0) {i = (i - 1) / 2;node[i] = (node[i * 2 + 1] + node[i * 2 + 2]);}}void add(LL i, LL x, LL a, LL b, LL l, LL r) {eval(i, a, b);if (b < l || r < a)return;if (l <= a&&b <= r) {lazy[i] += (b - a + 1)*x;eval(i, a, b);}else {add(i * 2 + 1, x, a, (a + b) / 2, l, r);add(i * 2 + 2, x, (a + b + 1) / 2, b, l, r);node[i] = node[i * 2 + 1] + node[i * 2 + 2];}}LL getsum(LL i, LL a, LL b, LL l, LL r) {eval(i, a, b);if (b < l || r < a)return 0;if (l <= a&&b <= r)return node[i];return (getsum(i * 2 + 1, a, (a + b) / 2, l, r) + getsum(i * 2 + 2, (a + b + 1) / 2, b, l, r));}};Seg seg(10000);int main() {cin >> n;cin >> w >> h;rep(i, n) {cin >> a[i].fi >> a[i].se >> a[i].th >> a[i].fo;if (a[i].fi < 0)a[i].fi = 0;a[i].ff = i;}sort(a, a + n, [](ene x, ene y) {return x.fo < y.fo; });rep(i, n) {seg.update(0, a[i].ff, 0, seg.n - 1, a[i].fi, a[i].th);}rep(i, 2000)seg.find(0, 0, seg.n - 1, i, i);for (int i = w; i <= h; i++)f[seg.node[i + seg.n - 1]] = true;rep(i, n)if (f[i])cout << 1 << endl;else cout << 0 << endl;return 0;}