oj.uz

Submission #302755

# Submission time Handle Problem Language Result Execution time Memory
302755 2020-09-19T06:48:56 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
17 / 100
 1180 ms 35940 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;

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;
    }
	return;
}

int compare_plants(int x, int y) {
    if(n <= 300) {
        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;
        }
    } 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 25344 KB Output is correct
2 Incorrect 15 ms 25344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25344 KB Output is correct
2 Correct 14 ms 25344 KB Output is correct
3 Correct 91 ms 28284 KB Output is correct
4 Correct 614 ms 35760 KB Output is correct
5 Correct 759 ms 35852 KB Output is correct
6 Correct 1022 ms 35816 KB Output is correct
7 Correct 1120 ms 35832 KB Output is correct
8 Correct 1180 ms 35824 KB Output is correct
9 Correct 689 ms 35940 KB Output is correct
10 Correct 705 ms 35696 KB Output is correct
11 Correct 559 ms 35812 KB Output is correct
12 Correct 679 ms 35852 KB Output is correct
13 Correct 796 ms 35796 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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