oj.uz

답안 #154587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154587 2019-09-23T01:32:08 Z AQT Sunčanje (COCI18_suncanje) C++14
39 / 130
 1091 ms 252160 KB 
#include <bits/stdc++.h>

using namespace std;

struct Node{
    int l, r;
    set<int> f, p, can, fcan; //full, part, candidate
};

int N, M;
bool ans[100005];
pair<int, int> arr[100005];
int xo[100005], xx[100005], yo[100005], yx[100005];
vector<int> cmp;
Node seg[600005];

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);
    if(!ans[v]){
        seg[idx].can.insert(v);
    }
    if(seg[idx].f.size() && *(--seg[idx].f.end()) > v){
        ans[v] = 1;
    }
    while(seg[idx].fcan.size() && *seg[idx].fcan.begin() < v){
        int n = *seg[idx].fcan.begin();
        seg[idx].fcan.erase(n);
        ans[n] = 1;
    }
    if(seg[idx].l == l && seg[idx].r == r){
        seg[idx].f.insert(v);
        seg[idx].fcan.insert(v);
        //cout << *seg[idx].can.begin() << endl;
        while(seg[idx].can.size() && *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);
        if(seg[idx].fcan.count(v)){
            seg[idx].fcan.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 >> xo[i] >> yo[i] >> xx[i] >> yx[i];
        xx[i] += xo[i];
        yx[i] += yo[i];
        yx[i]--;
        cmp.push_back(yo[i]);
        cmp.push_back(yx[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++){
        yo[i] = getidx(yo[i]), yx[i] = getidx(yx[i]);
        arr[i].first = xo[i];
        arr[i+N].first = xx[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++){
        if(arr[n].second > 0){
            add(yo[arr[n].second], yx[arr[n].second], arr[n].second, 1);
        }
        else{
            rem(yo[-arr[n].second], yx[-arr[n].second], -arr[n].second, 1);
        }
    }
    assert(seg[1].p.empty());
    for(int i = 1; i<=N; i++){
        if(ans[i]){
            cout << "NE\n";
        }
        else{
            cout << "DA\n";
        }
    }
}

/*
5
1 1 20 20
1 1 1 1
1 2 1 1
1 2 2 2
1 1 10 10

3
1 1 2 2
1 4 2 2
3 2 5 5
*/

Compilation message

suncanje.cpp: In function 'void build(int, int, int)':
suncanje.cpp:26:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l+r>>1;
               ~^~
suncanje.cpp: In function 'void add(int, int, int, int)':
suncanje.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = seg[idx].l + seg[idx].r >> 1;
               ~~~~~~~~~~~^~~~~~~~~~~~
suncanje.cpp: In function 'void rem(int, int, int, int)':
suncanje.cpp:84:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = seg[idx].l + seg[idx].r >> 1;
               ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 118392 KB Output is correct
2 Correct 159 ms 118628 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 119684 KB Output is correct
2 Correct 566 ms 122252 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 121724 KB Output is correct
2 Runtime error 631 ms 245088 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 592 ms 123196 KB Output is correct
2 Correct 636 ms 122540 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 806 ms 124740 KB Output is correct
2 Runtime error 330 ms 244824 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1091 ms 252160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 123560 KB Output is correct
2 Runtime error 337 ms 245236 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 343 ms 245532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 348 ms 245688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 356 ms 246612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -