oj.uz

답안 #321805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321805 2020-11-13T11:55:17 Z grt 식물 비교 (IOI20_plants) C++17
0 / 100
 71 ms 9324 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

struct Node {
    int g;
    pi f;
};

const int nax = 200000 + 10, INF = 1e9 + 10;
int n, k;
int val[nax];
int num[nax];
Node T[(1<<19)];

void prop(int x) {
    T[2*x].g += T[x].g;
    T[2*x+1].g += T[x].g;
    T[x].g = 0;
}

void upd(int a, int b, int l, int r, int v, int x) {
    if(a > b) return;
    if(a <= l && r <= b) {
        T[v].g += x;
        return;
    }
    prop(v);
    int mid = (l + r)/2;
    if(a <= mid) upd(a,b,l,mid,v*2,x);
    if(mid < b) upd(a,b,mid+1,r,v*2+1,x);
    T[v].f = min(make_pair(T[2*v].f.ST + T[2*v].g, T[2*v].f.ND), make_pair(T[2*v+1].f.ST + T[2*v+1].g, T[2*v+1].f.ND));
}

void ini(int l, int r, int v) {
    T[v].f.ND = l;
    if(l == r) {
        return;
    }
    int mid = (l + r)/2;
    ini(l,mid,v*2);
    ini(mid+1,r,v*2+1);
}

pi qr() {
    return {T[1].f.ST + T[1].g, T[1].f.ND};
}

set<int>zero;
set<int>candidate;

int d(int a, int b) {
    if(b >= a) return b - a;
    else return b - a + n;
}

void dodaj(int x) {
    if((int)zero.size() == 0) {
        zero.insert(x);
        candidate.insert(x);
        return;
    }
    auto it = zero.lower_bound(x);
    auto it2 = it;
    if(it2 == zero.begin()) {
        it2 = zero.end();
    }
    it2--;
    if(it == zero.end()) it = zero.begin();
    int pr = (*it2);
    int nx = (*it);
    if(d(x, nx) < k) {
        candidate.erase(nx);
    }
    if(d(pr, x) >= k) {
        candidate.insert(x);
    }
    zero.insert(x);
}

void usun(int x) {
    candidate.erase(x);
    zero.erase(x);
    if((int)zero.size() == 0) return;
    auto it = zero.lower_bound(x);
    auto it2 = it;
    if(it2 == zero.begin()) {
        it2 = zero.end();
    }
    it2--;
    if(it == zero.end()) it = zero.begin();
    if(d((*it2), (*it)) >= k) {
        candidate.insert((*it));
    }
}

void init(int K, vi r) {
    k = K;
    n = (int)r.size();
    ini(0, n-1,1);
    for(int i = 0; i < n; ++i) {
        upd(i,i,0,n-1,1,r[i]);
    }
    pi w = qr();
    while(w.ST == 0) {
        dodaj(w.ND);
        //zero.insert(w.ND);
        upd(w.ND,w.ND,0,n-1,1,INF);
        w = qr();
    }
    int cur = n;
    for(int step = 0; step < n; ++step) {
        auto it = candidate.begin();
        int x = (*it);
        //cout << x << " ";
        /*
        int x = -1, last = -1;
        for(auto y : zero) {
            if(last != -1) {
                if(y - last >= k) x = y;
            }
            last = y;
        }
        if(x == -1) x = (*zero.begin());
            */
        upd(max(0, x - k + 1), x - 1, 0, n - 1, 1, -1);
        upd(x - k + 1 + n, n - 1, 0, n - 1, 1, -1);
        usun(x);
        //zero.erase(x);
        w = qr();
        while(w.ST == 0) {
            dodaj(w.ND);
            //zero.insert(w.ND);
            upd(w.ND,w.ND,0,n-1,1,INF);
            w = qr();
        }
        num[x] = cur--;
    }
}

int compare_plants(int x, int y) {
    if(num[x] < num[y]) return -1;
    else return 1;
}

//int main() {
 //   init(3, {0, 1, 1, 2});
 //   cout << compare_plants(0, 2) << "\n";
 //   cout << compare_plants(1, 2) << "\n";
//}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6508 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Correct 4 ms 6508 KB Output is correct
4 Incorrect 4 ms 6508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6508 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Incorrect 4 ms 6528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6508 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Incorrect 4 ms 6528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6508 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Incorrect 71 ms 9324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Incorrect 4 ms 6508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6412 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Incorrect 4 ms 6508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6508 KB Output is correct
2 Correct 4 ms 6508 KB Output is correct
3 Correct 4 ms 6508 KB Output is correct
4 Incorrect 4 ms 6508 KB Output isn't correct
5 Halted 0 ms 0 KB -