oj.uz

Submission #302762

# Submission time Handle Problem Language Result Execution time Memory
302762 2020-09-19T07:13:59 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
0 / 100
 127 ms 29304 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]);
    }
    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 16 ms 25600 KB Output is correct
2 Correct 16 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 127 ms 29304 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
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 25336 KB Output is correct
6 Correct 20 ms 25472 KB Output is correct
7 Correct 108 ms 28664 KB Output is correct
8 Incorrect 30 ms 25472 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
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 25336 KB Output is correct
6 Correct 20 ms 25472 KB Output is correct
7 Correct 108 ms 28664 KB Output is correct
8 Incorrect 30 ms 25472 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25472 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 16 ms 25600 KB Output is correct
2 Correct 16 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 127 ms 29304 KB Output isn't correct
8 Halted 0 ms 0 KB -