oj.uz

답안 #305168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305168 2020-09-22T16:46:21 Z phathnv Sunčanje (COCI18_suncanje) C++11
0 / 130
 456 ms 58104 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "SUMCANJE"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int INF = 1e9;

struct rectangle{
    int x1, x2, y1, y2;
    rectangle(int _x1 = 0, int _x2 = 0, int _y1 = 0, int _y2 = 0){
        x1 = _x1;
        x2 = _x2;
        y1 = _y1;
        y2 = _y2;
    }
};

struct segmentTree{
    set <ii> d[N * 8];
    bool check(set <ii> &s, int l, int r){
        if (s.empty())
            return 1;
        auto it = s.lower_bound(mp(l, 0));
        if (it != s.end()){
            if ((*it).X <= r)
                return 0;
        }
        if (it != s.begin()){
            --it;
            if ((*it).Y >= l)
                return 0;
        }
        return 1;
    }
    void add(set <ii> &s, int l, int r){
        if (s.empty()){
            s.insert(mp(l, r));
            return;
        }

        auto first = s.upper_bound(mp(l, 0));
        auto last = s.upper_bound(mp(r, INF));
        if (first != s.begin()){
            --first;
            if ((*first).Y < l)
                ++first;
        }

        vector <ii> tmp;
        while (first != last){
            tmp.push_back(*first);
            ++first;
        }
        for(ii p : tmp){
            s.erase(p);
            l = min(l, p.X);
            r = max(r, p.Y);
        }
        s.insert(mp(l, r));
    }
    bool addRect(int id, int l, int r, int x1, int x2, int y1, int y2){
        if (x2 < l || r < x1)
            return 1;

        bool res = check(d[id], y1, y2);
        if (x1 <= l && r <= x2){
            add(d[id], y1, y2);
            return res;
        }
        int mid = (l + r) >> 1;
        res = res && addRect(id << 1, l, mid, x1, x2, y1, y2);
        res = res && addRect(id << 1 | 1, mid + 1, r, x1, x2, y1, y2);
        return res;
    }
} ST;

int n;
rectangle rect[N];

int x[2 * N], nX, y[2 * N], nY;
bool ans[N];

void readInput(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        int x, y, a, b;
        scanf("%d %d %d %d", &x, &y, &a, &b);
        rect[i] = rectangle(x, x + a - 1, y, y + b - 1);
    }
}

void prepare(){
    for(int i = 1; i <= n; i++){
        x[++nX] = rect[i].x1;
        x[++nX] = rect[i].x2;
        y[++nY] = rect[i].y1;
        y[++nY] = rect[i].y2;
    }
    sort(x + 1, x + 1 + nX);
    sort(y + 1, y + 1 + nY);
    nX = unique(x + 1, x + 1 + nX) - (x + 1);
    nY = unique(y + 1, y + 1 + nY) - (y + 1);
    for(int i = 1; i <= n; i++){
        rect[i].x1 = lower_bound(x + 1, x + 1 + nX, rect[i].x1) - x;
        rect[i].x2 = lower_bound(x + 1, x + 1 + nX, rect[i].x2) - x;
        rect[i].y1 = lower_bound(y + 1, y + 1 + nY, rect[i].y1) - y;
        rect[i].y2 = lower_bound(y + 1, y + 1 + nY, rect[i].y2) - y;
    }
}

void solve(){
    for(int i = n; i >= 1; i--)
        ans[i] = ST.addRect(1, 1, nX, rect[i].x1, rect[i].x2, rect[i].y1, rect[i].y2);
    for(int i = 1; i <= n; i++)
        if (ans[i])
            printf("DA\n");
        else
            printf("NE\n");
}

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    prepare();
    solve();
    return 0;
}

Compilation message

suncanje.cpp: In function 'void readInput()':
suncanje.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
suncanje.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d %d %d", &x, &y, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 40440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 41436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 43268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 44408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 50108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 198 ms 48888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 247 ms 51836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 57788 KB Output is correct
2 Incorrect 190 ms 47992 KB Output isn't correct

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 423 ms 57912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 456 ms 58104 KB Output isn't correct
2 Halted 0 ms 0 KB -