oj.uz

Submission #302749

# Submission time Handle Problem Language Result Execution time Memory
302749 2020-09-19T06:39:58 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
44 / 100
 1177 ms 36112 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(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 17 ms 25344 KB Output is correct
4 Incorrect 14 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 14 ms 25472 KB Output is correct
3 Correct 14 ms 25344 KB Output is correct
4 Correct 15 ms 25344 KB Output is correct
5 Correct 14 ms 25344 KB Output is correct
6 Correct 18 ms 25472 KB Output is correct
7 Correct 95 ms 28536 KB Output is correct
8 Correct 16 ms 25472 KB Output is correct
9 Correct 19 ms 25472 KB Output is correct
10 Correct 95 ms 28536 KB Output is correct
11 Correct 92 ms 28464 KB Output is correct
12 Correct 95 ms 28664 KB Output is correct
13 Correct 104 ms 28536 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 14 ms 25472 KB Output is correct
3 Correct 14 ms 25344 KB Output is correct
4 Correct 15 ms 25344 KB Output is correct
5 Correct 14 ms 25344 KB Output is correct
6 Correct 18 ms 25472 KB Output is correct
7 Correct 95 ms 28536 KB Output is correct
8 Correct 16 ms 25472 KB Output is correct
9 Correct 19 ms 25472 KB Output is correct
10 Correct 95 ms 28536 KB Output is correct
11 Correct 92 ms 28464 KB Output is correct
12 Correct 95 ms 28664 KB Output is correct
13 Correct 104 ms 28536 KB Output is correct
14 Correct 154 ms 29216 KB Output is correct
15 Correct 1146 ms 35944 KB Output is correct
16 Correct 164 ms 29176 KB Output is correct
17 Correct 1177 ms 35816 KB Output is correct
18 Correct 770 ms 35736 KB Output is correct
19 Correct 741 ms 35816 KB Output is correct
20 Correct 1016 ms 35816 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 83 ms 28280 KB Output is correct
4 Correct 608 ms 35816 KB Output is correct
5 Correct 736 ms 35944 KB Output is correct
6 Correct 961 ms 35944 KB Output is correct
7 Correct 1092 ms 35912 KB Output is correct
8 Correct 1173 ms 35940 KB Output is correct
9 Correct 659 ms 35932 KB Output is correct
10 Correct 662 ms 35816 KB Output is correct
11 Correct 528 ms 35816 KB Output is correct
12 Correct 611 ms 35984 KB Output is correct
13 Correct 765 ms 36112 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 16 ms 25472 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 17 ms 25344 KB Output is correct
4 Incorrect 14 ms 25344 KB Output isn't correct
5 Halted 0 ms 0 KB -