#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
//#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
//#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
using namespace std;
const int maxn = (int)4e5 + 10;
const int mod = (int)1e9 + 7;
#define inf mod
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> Vll;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, x1[maxn / 4], x2[maxn / 4], y11[maxn / 4], y2[maxn / 4], a, b, t[4][maxn], M;
vi vals;
inline void upd(int type, int pos, int val){
for(; pos < M; pos |= (pos + 1))
t[type][pos] += val;
}
inline int get(int type, int r){
int res = 0;
for(; r >= 0; r = (r & (r + 1)) - 1)
res += t[type][r];
return res;
}
inline int get(int type, int l, int r){
return get(type, r) - get(type, l - 1);
}
struct node{
node *l, *r;
int pr, sz, key, lz;
node(){
l = r = NULL;
pr = sz = key = lz = 0;
}
node (int _key){
key = _key;
l = r = NULL;
sz = 1;
lz = 0;
pr = uniform_int_distribution<>(0, inf)(rng);
}
};
typedef node* pnode;
pnode root[4][maxn];
inline int sz(pnode t) {
return t ? t->sz : 0;
}
inline pnode copy(pnode t) {
return new node(t->key);
}
inline void upd_sz(pnode &t) {
if(t)
t->sz = sz(t->l) + 1 + sz(t->r);
}
void split(pnode t, pnode &l, pnode &r, int key) {
if(!t){
r = l = NULL;
return;
}
if(t -> key <= key)
split(t -> r, t -> r, r, key), l = t;
else
split(t -> l, l, t -> l, key), r = t;
upd_sz(l);
upd_sz(r);
}
void merge(pnode &t, pnode l, pnode r) {
if(!l || !r)
t = l ? l : r;
else if(l -> pr > r -> pr)
merge(l -> r, l -> r, r), t = l;
else
merge(r -> l, l, r -> l), t = r;
upd_sz(t);
}
inline void insert(pnode &t1, pnode t2){
pnode tl, tr;
split(t1, tl, tr, t2 -> key);
merge(tl, tl, copy(t2));
merge(t1, tl, tr);
}
int get(pnode &t, int key) {
if(t == NULL) return 0;
pnode cur1, cur2;
split(t, cur1, cur2, key);
int res = sz(cur1);
merge(t, cur1, cur2);
return res;
}
inline void add(int type, int x, int y, int val){
for(; x < M; x |= (x + 1)){
insert(root[type][x], new node(y));
}
}
inline int Sum(int type, int x, int y){
int res = 0;
for(; x >= 0; x = (x & (x + 1)) - 1)
res += get(root[type][x], y);
return res;
}
ll bad[maxn];
int R() {
char c;
int ans = 0;
bool started = 0, is_negative = 0;
while (true) {
c = getchar();
if ((c < '0' || c > '9') && c != '-' && !started) continue;
if ((c < '0' || c > '9') && c != '-' && started) break;
if (started)
ans = ans * 10;
started = 1;
if (c == '-') is_negative = 1;
else ans += c - '0';
}
if (is_negative)
ans = -ans;
return ans;
}
inline void solve () {
n = R();
forn(i, 1, n){
x1[i] = R(); y11[i] = R();
x2[i] = x1[i] + R();
y2[i] = y11[i] + R();
vals.pb(x1[i]);
vals.pb(x2[i]);
vals.pb(y11[i]);
vals.pb(y2[i]);
}
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
M = vals.size();
forn(i, 0, maxn - 1)
root[0][i] = root[1][i] = root[2][i] = root[3][i] = NULL;
forn(i, 1, n){
x1[i] = lower_bound(all(vals), x1[i]) - vals.begin();
x2[i] = lower_bound(all(vals), x2[i]) - vals.begin();
y11[i] = lower_bound(all(vals), y11[i]) - vals.begin();
y2[i] = lower_bound(all(vals), y2[i]) - vals.begin();
}
forev(i, n, 1){
int c1 = get(0, x2[i] + 1, M - 1);
int c2 = get(1, y2[i] + 1, M - 1);
int c4 = get(2, x1[i] - 1);
int c5 = get(3, y11[i] - 1);
upd(0, x1[i], 1);
upd(1, y11[i], 1);
upd(2, x2[i], 1);
upd(3, y2[i], 1);
ll cur = c1 + c2 + c4 + c5;
cur -= Sum(0, x1[i] - 1, y11[i] - 1);
add(0, x2[i], y2[i], 1);
cur -= Sum(1, M - x2[i] - 2, M - y2[i] - 2);
add(1, M - x1[i] - 1, M - y11[i] - 1, 1);
cur -= Sum(2, M - x2[i] - 2, y11[i] - 1);
add(2, M - x1[i] - 1, y2[i], 1);
cur -= Sum(3, x1[i] - 1, M - y2[i] - 2);
add(3, x2[i], M - y11[i] - 1, 1);
bad[i] = cur;
}
forn(i, 1, n){
puts(bad[i] == n - i ? "DA" : "NE");
}
}
int main () {
int tt = 1;
//cin >> tt;
forn(i, 1, tt)
solve();
}
Compilation message
suncanje.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
27896 KB |
Output is correct |
| 2 |
Correct |
230 ms |
33912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
506 ms |
52848 KB |
Output is correct |
| 2 |
Correct |
3012 ms |
172320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1176 ms |
87404 KB |
Output is correct |
| 2 |
Execution timed out |
4051 ms |
207440 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1866 ms |
117364 KB |
Output is correct |
| 2 |
Correct |
3188 ms |
177984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3665 ms |
182276 KB |
Output is correct |
| 2 |
Execution timed out |
4032 ms |
207384 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3804 ms |
193004 KB |
Output is correct |
| 2 |
Execution timed out |
4062 ms |
210432 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3976 ms |
192516 KB |
Output is correct |
| 2 |
Execution timed out |
4064 ms |
206488 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4062 ms |
202092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4043 ms |
207524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4050 ms |
207864 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
