Submission #750488

#	Time	Username	Problem	Language	Result	Execution time	Memory
750488		Trunkty	Sunčanje (COCI18_suncanje)	C++14	0 / 130	845 ms	262144 KiB

suncanje

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n;
int arr[100005][5];
int nex;
set<int> s;
map<int,int> coorcomp;
bool ans[100005];

//

set<pair<int,int>> segtree[1600005];
vector<pair<int,int>> lazy[1600005];

void toadd(int node, int a, int b){
    while(1){
        auto it = segtree[node].lower_bound({a,b});
        if(it==segtree[node].end()){
            break;
        }
        if((*it).first<=b){
            b = max(b,(*it).second);
            segtree[node].erase(it);
        }
        else{
            break;
        }
    }
    while(1){
        auto it = segtree[node].lower_bound({a,b});
        if(it==segtree[node].begin()){
            break;
        }
        it--;
        if((*it).second>=a){
            a = min(a,(*it).first);
            segtree[node].erase(it);
        }
        else{
            break;
        }
    }
    segtree[node].insert({a,b});
}

void pushdown(int node, int l, int r){
    for(pair<int,int> i:lazy[node]){
        toadd(node,i.first,i.second);
        if(l!=r){
            lazy[node*2].push_back(i);
            lazy[node*2+1].push_back(i);
        }
    }
    lazy[node].clear();
}

void update(int node, int l, int r, int needl, int needr, int a, int b){
    pushdown(node,l,r);
    if(l>needr or r<needl){
        return;
    }
    else if(l>=needl and r<=needr){
        lazy[node].push_back({a,b});
        pushdown(node,l,r);
    }
    else{
        int mid = (l+r)/2;
        update(node*2,l,mid,needl,needr,a,b);
        update(node*2+1,mid+1,r,needl,needr,a,b);
        toadd(node,a,b);
    }
}

bool query(int node, int l, int r, int needl, int needr, int a, int b){
    pushdown(node,l,r);
    if(l>needr or r<needl){
        return false;
    }
    else if(l>=needl and r<=needr){
        auto it = segtree[node].lower_bound({a,b});
        if(it!=segtree[node].end() and (*it).first<=b){
            return true;
        }
        if(it!=segtree[node].begin() and (*prev(it)).second>=a){
            return true;
        }
        return false;
    }
    else{
        int mid = (l+r)/2;
        return (query(node*2,l,mid,needl,needr,a,b) or query(node*2+1,mid+1,r,needl,needr,a,b));
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        arr[i][1] = a+1;
        arr[i][2] = a+c;
        arr[i][3] = b+1;
        arr[i][4] = b+d;
        s.insert(a+1);
        s.insert(a+c);
        s.insert(b+1);
        s.insert(b+d);
    }
    for(int i:s){
        nex++;
        coorcomp[i] = nex;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=4;j++){
            arr[i][j] = coorcomp[arr[i][j]];
        }
    }
    for(int i=n;i>=1;i--){
        if(!query(1,1,4e5,arr[i][1],arr[i][2],arr[i][3],arr[i][4])){
            ans[i] = true;
        }
        update(1,1,4e5,arr[i][1],arr[i][2],arr[i][3],arr[i][4]);
    }
    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout << "DA" << "\n";
        }
        else{
            cout << "NE" << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13