| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 154580 | AQT | Sunčanje (COCI18_suncanje) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Node{
int l, r;
set<int> f, p, can; //full, part, candidate
};
int N, M;
bool ans[100005];
vector<int> cmp;
pair<int, int> arr[100005];
Node seg[1000000];
int xo[100005], xn[100005], yo[100005], yn[100005];
int getidx(int n){
return lower_bound(cmp.begin(), cmp.end(), n) - cmp.begin() + 1;
}
void build(int l, int r, int idx){
seg[idx].l = l, seg[idx].r = r;
if(l == r){
return;
}
int mid = l+r>>1;
build(l, mid, 2*idx);
build(mid+1, r, 2*idx+1);
}
void add(int l, int r, int v, int idx){
//cout << l << " " << r << " " << v << endl;
seg[idx].p.insert(v);
seg[idx].can.insert(v);
if(seg[idx].f.size() && *(--seg[idx].f.end()) > v){
ans[v] = 1;
}
if(seg[idx].l == l && seg[idx].r == r){
seg[idx].f.insert(v);
//cout << *seg[idx].can.begin() << endl;
while(*seg[idx].can.begin() < v){
int n = *seg[idx].can.begin();
seg[idx].can.erase(n);
ans[n] = 1;
}
if(*(--seg[idx].p.end()) > v){
ans[v] = 1;
}
return;
}
int mid = seg[idx].l + seg[idx].r >> 1;
if(r <= mid){
add(l, r, v, 2*idx);
}
else if(l > mid){
add(l, r, v, 2*idx+1);
}
else{
add(l, mid, v, 2*idx);
add(mid+1, r, v, 2*idx+1);
}
}
void rem(int l, int r, int v, int idx){
seg[idx].p.erase(v);
if(seg[idx].can.count(v)){
seg[idx].can.erase(v);
}
if(seg[idx].l == l && seg[idx].r == r){
seg[idx].f.erase(v);
return;
}
int mid = seg[idx].l + seg[idx].r >> 1;
if(r <= mid){
rem(l, r, v, 2*idx);
}
else if(l > mid){
rem(l, r, v, 2*idx+1);
}
else{
rem(l, mid, v, 2*idx);
rem(mid+1, r, v, 2*idx+1);
}
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i = 1; i<=N; i++){
cin >> x1[i] >> y11[i] >> x2[i] >> y2[i];
x2[i] += x1[i];
y2[i] += y11[i];
y2[i]--;
cmp.push_back(y11[i]);
cmp.push_back(y2[i]);
}
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
M = cmp.size();
build(1, M, 1);
for(int i = 1; i<=N; i++){
y11[i] = getidx(y11[i]), y2[i] = getidx(y2[i]);
arr[i].first = x1[i];
arr[i+N].first = x2[i];
arr[i].second = i;
arr[i+N].second = -i;
}
sort(arr+1, arr+1+2*N);
for(int n = 1; n<=2*N; n++){
//cout << arr[n].second << endl;
if(arr[n].second > 0){
add(y11[arr[n].second], y2[arr[n].second], arr[n].second, 1);
}
else{
rem(y11[-arr[n].second], y2[-arr[n].second], -arr[n].second, 1);
}
}
for(int i = 1; i<=N; i++){
if(ans[i]){
cout << "NE\n";
}
else{
cout << "DA\n";
}
}
}