oj.uz

Submission #302758

# Submission time Handle Problem Language Result Execution time Memory
302758 2020-09-19T07:04:36 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
44 / 100
 1409 ms 45980 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;
        }
        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.end());
        if(p > h[i]) {
            s.insert(h[i]);
            ans0[i] = 1;
        }
        if(i >= k-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 25472 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Incorrect 15 ms 25344 KB Output isn't correct
5 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 25344 KB Output is correct
5 Correct 17 ms 25344 KB Output is correct
6 Correct 19 ms 25472 KB Output is correct
7 Correct 100 ms 28664 KB Output is correct
8 Correct 30 ms 25472 KB Output is correct
9 Correct 20 ms 25472 KB Output is correct
10 Correct 104 ms 28664 KB Output is correct
11 Correct 101 ms 28536 KB Output is correct
12 Correct 97 ms 28792 KB Output is correct
13 Correct 103 ms 28684 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 25344 KB Output is correct
5 Correct 17 ms 25344 KB Output is correct
6 Correct 19 ms 25472 KB Output is correct
7 Correct 100 ms 28664 KB Output is correct
8 Correct 30 ms 25472 KB Output is correct
9 Correct 20 ms 25472 KB Output is correct
10 Correct 104 ms 28664 KB Output is correct
11 Correct 101 ms 28536 KB Output is correct
12 Correct 97 ms 28792 KB Output is correct
13 Correct 103 ms 28684 KB Output is correct
14 Correct 171 ms 29688 KB Output is correct
15 Correct 1326 ms 41956 KB Output is correct
16 Correct 168 ms 29448 KB Output is correct
17 Correct 1352 ms 43240 KB Output is correct
18 Correct 827 ms 41292 KB Output is correct
19 Correct 809 ms 41192 KB Output is correct
20 Correct 1129 ms 43596 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 88 ms 28408 KB Output is correct
4 Correct 694 ms 43688 KB Output is correct
5 Correct 840 ms 45576 KB Output is correct
6 Correct 1151 ms 44584 KB Output is correct
7 Correct 1346 ms 44776 KB Output is correct
8 Correct 1409 ms 45416 KB Output is correct
9 Correct 738 ms 45672 KB Output is correct
10 Correct 753 ms 41700 KB Output is correct
11 Correct 612 ms 45892 KB Output is correct
12 Correct 720 ms 45980 KB Output is correct
13 Correct 855 ms 43492 KB Output is correct

Subtask #5
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 Incorrect 15 ms 25344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 15 ms 25344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25472 KB Output is correct
2 Correct 15 ms 25344 KB Output is correct
3 Correct 15 ms 25344 KB Output is correct
4 Incorrect 15 ms 25344 KB Output isn't correct
5 Halted 0 ms 0 KB -