oj.uz

Submission #428775

# Submission time Handle Problem Language Result Execution time Memory
428775 2021-06-15T14:25:23 Z MarcoMeijer Comparing Plants (IOI20_plants) C++14
17 / 100
 1711 ms 58700 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (1<<20);

int n, k;
vi r;

struct Seg {
    ii mn[N*2]; int laz[N*2];
    void build(int p=1, int l=0, int r=N-1) {
        laz[p] = 0;
        if(l == r) {
            mn[p] = {0,l};
            return;
        }
        int m=(l+r)/2;
        build(p*2  ,l  ,m);
        build(p*2+1,m+1,r);
        mn[p] = min(mn[p*2],mn[p*2+1]);
    }
    void add(int p, int v) {
        laz[p] += v;
        mn[p] = {mn[p].fi+v, mn[p].se};
    }
    void pushDown(int p) {
        add(p*2  ,laz[p]);
        add(p*2+1,laz[p]);
        laz[p] = 0;
    }
    void add(int i, int j, int v, int p=1, int l=0, int r=N-1) {
        if(j < l || i > r) return;
        if(i <= l && j >= r) {
            add(p,v);
            return;
        }
        pushDown(p);
        int m=(l+r)/2;
        add(i,j,v,p*2,l,m);
        add(i,j,v,p*2+1,m+1,r);
        mn[p] = min(mn[p*2],mn[p*2+1]);
    }
    ii get(int i, int j, int p=1, int l=0, int r=N-1) {
        if(j < l || i > r) return {INF,INF};
        if(i <= l && j >= r) return mn[p];
        pushDown(p);
        int m=(l+r)/2;
        ii a = get(i,j,p*2,l,m);
        ii b = get(i,j,p*2+1,m+1,r);
        return min(a,b);
    }
    void addCircle(int i, int l, int v) {
        int j = i + l - 1;
        add(i,min(n-1,j),v);
        if(j > n-1)
            add(0,j-n,v);
    }
};

Seg seg1, seg2;

vi val;
vector<vi> dist1, dist2;

void init(int k_, vi r_) {
    k = k_; r = r_;
    n = r.size();
    seg1.build(); seg2.build();
    RE(i,n) seg1.add(i,i,r[i]);
    RE(i,n) seg2.add(i,i,1);

    val.assign(n,0);
    REV(i,0,n) {
        while(true) {
            ii res = seg1.get(0,n-1);
            if(res.fi != 0)
                break;
            int j = res.se;
            seg1.add(j,j,INF);
            seg2.add(j,j,-1);
            seg2.addCircle((j+1)%n, k-1, 1);
        }

        ii res = seg2.get(0,n-1);
        int j = res.se;
        val[j] = i;
        seg2.add(j,j,INF);
        seg2.addCircle((j+1)%n, k-1, -1);
        seg1.addCircle((j-k+n+1)%n, k-1, -1);
    }

    if(n <= 300) {
        dist1.assign(n,vi(n,1e9));
        RE(i,n) dist1[i][i] = 0;
        RE(i,n) RE(j,k-1) {
            int x = (i+j+1)%n;
            if(val[i] > val[x])
                dist1[i][x] = 0;
        }
        RE(i,n) RE(j,n) RE(k,n) dist1[i][k] = min(dist1[i][k], dist1[i][j] + dist1[j][k]);

        dist2.assign(n,vi(n,1e9));
        RE(i,n) dist2[i][i] = 0;
        RE(i,n) RE(j,k-1) {
            int x = (i+j+1)%n;
            if(val[i] < val[x])
                dist2[i][x] = 0;
        }
        RE(i,n) RE(j,n) RE(k,n) dist2[i][k] = min(dist2[i][k], dist2[i][j] + dist2[j][k]);
    }
}

int compare_plants(int x, int y) {
    if(n <= 300) {
        if(dist1[x][y] == 0)
            return 1;
        if(dist2[x][y] == 0)
            return -1;
        return 0;
    }
	return val[x] > val[y] ? 1 : -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 49512 KB Output is correct
2 Incorrect 42 ms 49516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 49512 KB Output is correct
2 Incorrect 42 ms 49516 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 45 ms 49512 KB Output is correct
2 Correct 49 ms 49448 KB Output is correct
3 Correct 107 ms 54116 KB Output is correct
4 Correct 991 ms 57936 KB Output is correct
5 Correct 1103 ms 58120 KB Output is correct
6 Correct 1363 ms 58304 KB Output is correct
7 Correct 1565 ms 58504 KB Output is correct
8 Correct 1711 ms 58700 KB Output is correct
9 Correct 1025 ms 58044 KB Output is correct
10 Correct 1022 ms 58056 KB Output is correct
11 Correct 892 ms 58052 KB Output is correct
12 Correct 1063 ms 58136 KB Output is correct
13 Correct 1256 ms 58164 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49492 KB Output is correct
2 Incorrect 41 ms 49436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49420 KB Output is correct
2 Incorrect 43 ms 49540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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