oj.uz

Submission #575486

# Submission time Handle Problem Language Result Execution time Memory
575486 2022-06-10T19:09:20 Z czhang2718 Sunčanje (COCI18_suncanje) C++17
130 / 130
 1104 ms 143420 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define f first
#define s second
#define nl "\n"
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MOD=1e9+7;
 
const int N=4e5+1;
int n;
int a[N], b[N], c[N], d[N];
bool bad[N];
int M;
 
set<int> se[4*N];
int mn[4*N];
int mx[4*N];
 
// range insert
// range kill
// range get max

void ins(int l, int r, int i, int x=0, int lx=0, int rx=M+1){
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
        se[x].insert(i);
        mn[x]=*se[x].begin();
        mx[x]=*--se[x].end();
        if(rx-lx>1){
            mn[x]=min({mn[x], mn[2*x+1], mn[2*x+2]});
            mx[x]=max({mx[x], mx[2*x+1], mx[2*x+2]});
        }
        return;
    }
    int m=(lx+rx)/2;
    ins(l, r, i, 2*x+1, lx, m);
    ins(l, r, i, 2*x+2, m, rx);
    mn[x]=min({sz(se[x])?*se[x].begin():(int)1e9, mn[2*x+1], mn[2*x+2]});
    mx[x]=max({sz(se[x])?*--se[x].end():0, mx[2*x+1], mx[2*x+2]});
}
 

int get_min(int l, int r, int x=0, int lx=0, int rx=M+1){
    if(lx>=r || rx<=l) return 1e9;
    if(lx>=l && rx<=r) return mn[x];
    int m=(lx+rx)/2;
    return min({sz(se[x])?*se[x].begin():(int)1e9, get_min(l, r, 2*x+1, lx, m), get_min(l, r, 2*x+2, m, rx)});
}

 
int get_max(int l, int r, int x=0, int lx=0, int rx=M+1){
    if(lx>=r || rx<=l) return 0;
    if(lx>=l && rx<=r) return mx[x];
    int m=(lx+rx)/2;
    return max({sz(se[x])?*--se[x].end():0, get_max(l, r, 2*x+1, lx, m), get_max(l, r, 2*x+2, m, rx)});
}
 
 
void del(int l, int r, int i, int x=0, int lx=0, int rx=M+1){
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
        if(se[x].find(i)==se[x].end()) return;
        se[x].erase(i);
        mn[x]=se[x].size()?*se[x].begin():1e9;
        mx[x]=se[x].size()?*--se[x].end():0;
        if(rx-lx>1){
            mn[x]=min({mn[x], mn[2*x+1], mn[2*x+2]});
            mx[x]=max({mx[x], mx[2*x+1], mx[2*x+2]});
        }
        return;
    }
    int m=(lx+rx)/2;
    del(l, r, i, 2*x+1, lx, m);
    del(l, r, i, 2*x+2, m, rx);
    mn[x]=min({sz(se[x])?*se[x].begin():(int)1e9, mn[2*x+1], mn[2*x+2]});
    mx[x]=max({sz(se[x])?*--se[x].end():0, mx[2*x+1], mx[2*x+2]});
}

 
int main(){
  cin.tie(0)->sync_with_stdio(0);
 
    cin >> n;
    set<int> s;
    map<int, int> mp;
    vi xs;
    map<int, vi> st, nd;

    rep(i,1,n){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        c[i]+=a[i]-1;
        d[i]+=b[i]-1;
        xs.pb(a[i]); xs.pb(c[i]);
        st[a[i]].pb(i);
        nd[c[i]].pb(i);
        s.insert(b[i]);
        s.insert(d[i]);
    }
    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
  
    M=sz(s);

    int cnt=0;
    for(int x:s){
        mp[x]=++cnt;
    }

    rep(i,1,n){
        b[i]=mp[b[i]];
        d[i]=mp[d[i]];
    }
 
 
    //sweep line 1
    for(int x:xs){
        for(int i:st[x]){
            int y1=b[i];
            int y2=d[i];
            ins(y1, y2+1, i);
        }
        for(int i:st[x]){
            int y1=b[i];
            int y2=d[i];
            int mx=get_max(y1, y2+1);
            if(mx>i) bad[i]=1;
        }
        for(int i:nd[x]){
            int y1=b[i];
            int y2=d[i];
            del(y1, y2+1, i);
        }
    }

    rep(i,0,4*M+4) mn[i]=1e9, mx[i]=0, se[i].clear();

    // sweep line 2
    for(int x:xs){
        for(int i:st[x]){
            int y1=b[i];
            int y2=d[i];
            ins(y1, y2+1, i);
        }
        for(int i:st[x]){
            int y1=b[i];
            int y2=d[i];
            while(true){
                int die=get_min(y1, y2+1);
                // cout << i << " min " << die << nl;
                if(die>=i) break;
                // cout << "del " << die << nl;
                bad[die]=1;
                del(b[die], d[die]+1, die);
            }
        }
        for(int i:nd[x]){
            int y1=b[i];
            int y2=d[i];
            del(y1, y2+1, i);
        }
    }


    rep(i,1,n) cout << (bad[i]?"NE":"DA") << nl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 78688 KB Output is correct
2 Correct 71 ms 80284 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 83692 KB Output is correct
2 Correct 390 ms 106288 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 90268 KB Output is correct
2 Correct 468 ms 113456 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 96316 KB Output is correct
2 Correct 384 ms 107188 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 107888 KB Output is correct
2 Correct 536 ms 116148 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 108956 KB Output is correct
2 Correct 508 ms 113584 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 108196 KB Output is correct
2 Correct 705 ms 120908 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 123168 KB Output is correct
2 Correct 531 ms 110332 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 127428 KB Output is correct
2 Correct 753 ms 130340 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 139840 KB Output is correct
2 Correct 961 ms 143420 KB Output is correct