oj.uz

Submission #302763

# Submission time Handle Problem Language Result Execution time Memory
302763 2020-09-19T07:14:37 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
70 / 100
 1416 ms 43624 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=4e5+100;

int n, k;
vi r;
int h[MX];

struct Seg {
    ii SEG[MX*4]; int LAZY[MX*4];
    void build(const vi& f, int p=0, int l=0, int r=n-1) {
        LAZY[p] = 0;
        if(l == r) {
            SEG[p] = {f[l], l};
            return;
        }
        int m=(l+r)/2;
        build(f,p*2+1,l,m);
        build(f,p*2+2,m+1,r);
        SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
    }
    void add(int i, int j, int v, int lazy=0, int p=0, int l=0, int r=n-1) {
        LAZY[p] += lazy;
        SEG[p].fi += lazy;
        if(j < l || i > r) return;
        if(i <= l && j >= r) {
            SEG[p].fi += v;
            LAZY[p] += v;
            return;
        }
        int m=(l+r)/2;
        add(i,j,v,LAZY[p],p*2+1,l,m);
        add(i,j,v,LAZY[p],p*2+2,m+1,r);
        LAZY[p] = 0;
        SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
    }
    void addRound(int i, int j, int v) {
        if(i >= n) i-=n, j-=n;
        if(j < n) {
            add(i,j,v);
        } else {
            add(i,n-1,v);
            add(0,j-n,v);
        }
    }
} seg1, seg2;

int ans0[MX];

void fill0() {
    int x=0, y=n-1;
    RE(i,n) ans0[i] = 0;
    set<int> s; s.insert(h[x]);
    REP(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *s.begin();
        if(p < h[i]) {
            s.insert(h[i]);
            ans0[i] = -1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
    s.clear(); s.insert(h[x]);
    REP(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *(--s.end());
        if(p > h[i]) {
            s.insert(h[i]);
            ans0[i] = 1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
    s.clear(); s.insert(h[x]);
    REV(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *s.begin();
        if(p < h[i]) {
            s.insert(h[i]);
            ans0[i] = -1;
        }
        s.erase(h[i+k-1]);
    }
    s.clear(); s.insert(h[x]);
    REV(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *(--s.end());
        if(p > h[i]) {
            s.insert(h[i]);
            ans0[i] = 1;
        }
        s.erase(h[i+k-1]);
    }
}
void init(int _k, vi _r) {
    k = _k; r = _r;
    n = r.size();

    seg1.build(r);
    seg2.build(vi(n,0));

    RE(i,n) {
        while(seg1.SEG[0].fi == k-1) {
            int x = seg1.SEG[0].se;
            seg1.add(x,x,-INF);
            seg2.add(x,x,1);
            seg2.addRound(x+1,x+k-1,-1);
        }

        int x = seg2.SEG[0].se;
        seg2.add(x,x,-INF);
        seg2.addRound(x+1,x+k-1,1);
        seg1.addRound(x+n-k+1,x+n-1,1);
        h[x] = h[x+n] = i;
    }
    fill0();
	return;
}

int comp(int x, int y) {
    if(y < x) y += n;
    if(h[x] < h[y]) {
        set<int> s; s.insert(h[x]);
        REP(i,x+1,y+1) {
            if(s.empty()) break;
            int p = *s.begin();
            if(p < h[i]) {
                s.insert(h[i]);
            }
            if(i >= k-1) s.erase(h[i-k+1]);
        }
        if(s.count(h[y])) return -1;
        return 0;
    } else {
        set<int> s; s.insert(h[x]);
        REP(i,x+1,y+1) {
            if(s.empty()) break;
            int p = *(--s.end());
            if(p > h[i]) {
                s.insert(h[i]);
            }
            if(i >= k-1) s.erase(h[i-k+1]);
        }
        if(s.count(h[y])) return 1;
        return 0;
    }
}
int compare_plants(int x, int y) {
    if(x == 0) {
        return ans0[y];
    } else if(n <= 300) {
        int res = comp(x,y);
        if(res != 0) return res;
        res = comp(y,x);
        return -res;
    } else {
        if(h[x] < h[y]) return -1;
        else return 1;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25344 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 117 ms 28280 KB Output is correct
7 Incorrect 125 ms 29304 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25472 KB Output is correct
5 Correct 16 ms 25472 KB Output is correct
6 Correct 20 ms 25472 KB Output is correct
7 Correct 99 ms 28664 KB Output is correct
8 Correct 29 ms 25472 KB Output is correct
9 Correct 19 ms 25472 KB Output is correct
10 Correct 100 ms 28664 KB Output is correct
11 Correct 92 ms 28536 KB Output is correct
12 Correct 93 ms 28664 KB Output is correct
13 Correct 98 ms 28664 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25472 KB Output is correct
5 Correct 16 ms 25472 KB Output is correct
6 Correct 20 ms 25472 KB Output is correct
7 Correct 99 ms 28664 KB Output is correct
8 Correct 29 ms 25472 KB Output is correct
9 Correct 19 ms 25472 KB Output is correct
10 Correct 100 ms 28664 KB Output is correct
11 Correct 92 ms 28536 KB Output is correct
12 Correct 93 ms 28664 KB Output is correct
13 Correct 98 ms 28664 KB Output is correct
14 Correct 176 ms 29352 KB Output is correct
15 Correct 1383 ms 39912 KB Output is correct
16 Correct 170 ms 29432 KB Output is correct
17 Correct 1382 ms 40808 KB Output is correct
18 Correct 858 ms 41336 KB Output is correct
19 Correct 840 ms 41400 KB Output is correct
20 Correct 1298 ms 43624 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 85 ms 28408 KB Output is correct
4 Correct 627 ms 36580 KB Output is correct
5 Correct 758 ms 36712 KB Output is correct
6 Correct 1060 ms 36708 KB Output is correct
7 Correct 1268 ms 37092 KB Output is correct
8 Correct 1416 ms 40552 KB Output is correct
9 Correct 667 ms 36580 KB Output is correct
10 Correct 699 ms 36836 KB Output is correct
11 Correct 537 ms 36548 KB Output is correct
12 Correct 643 ms 36588 KB Output is correct
13 Correct 823 ms 39528 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25376 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 24 ms 25472 KB Output is correct
7 Correct 241 ms 26096 KB Output is correct
8 Correct 597 ms 26104 KB Output is correct
9 Correct 577 ms 26104 KB Output is correct
10 Correct 606 ms 26104 KB Output is correct
11 Correct 260 ms 25984 KB Output is correct
12 Correct 429 ms 26104 KB Output is correct
13 Correct 396 ms 26104 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25344 KB Output is correct
5 Correct 18 ms 25472 KB Output is correct
6 Correct 734 ms 36696 KB Output is correct
7 Correct 1020 ms 36712 KB Output is correct
8 Correct 1237 ms 37220 KB Output is correct
9 Correct 1368 ms 40808 KB Output is correct
10 Correct 657 ms 36712 KB Output is correct
11 Correct 1016 ms 39528 KB Output is correct
12 Correct 614 ms 36712 KB Output is correct
13 Correct 738 ms 36712 KB Output is correct
14 Correct 1037 ms 36720 KB Output is correct
15 Correct 1249 ms 36968 KB Output is correct
16 Correct 654 ms 36568 KB Output is correct
17 Correct 722 ms 36712 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Correct 15 ms 25344 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 117 ms 28280 KB Output is correct
7 Incorrect 125 ms 29304 KB Output isn't correct
8 Halted 0 ms 0 KB -