oj.uz

Submission #308342

# Submission time Handle Problem Language Result Execution time Memory
308342 2020-10-01T00:46:58 Z bruce_test Comparing Plants (IOI20_plants) C++11
25 / 100
 189 ms 25960 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7, MM = 2e5+5;
int N, K, lz[4*MM], mi[4*MM], stk[MM], tp=-1; vi ord1, ord2;
void pushdn(int rt){
    mi[lc]+=lz[rt]; mi[rc]+=lz[rt];
    lz[lc]+=lz[rt]; lz[rc]+=lz[rt]; lz[rt]=0;
}
void upd(int L, int R, int l, int r, int val, int rt){
    if(r < L || l > R) return;
    if(l <= L && R <= r){ mi[rt]+=val; lz[rt]+=val; return; }
    if(lz[rt]) pushdn(rt);
    int mid = (L+R)/2;
    if(l <= mid) upd(L, mid, l, r, val, lc);
    if(r > mid) upd(mid+1, R, l, r, val, rc);
    mi[rt] = min(mi[lc], mi[rc]);
}
int qry(int L, int R, int rt){
    if(mi[rt] > 0) return -1;
    if(L==R) return L;
    if(lz[rt]) pushdn(rt);
    int mid = (L+R)/2;
    if(mi[lc] > 0) return qry(mid+1, R, rc);
    return qry(L, mid, lc);
}
vi solve(vi& r){
    vi ret(N); cl(lz, 0); cl(mi, 0);
    for(int i=0; i<N; i++)
        upd(0, N-1, i, i, r[i], 1);
    for(int i=0; i<N; i++){
        int pos = qry(0, N-1, 1);
        while(pos < 0 && tp >= 0){
            upd(0, N-1, stk[tp--], N-1, -1, 1);
            pos = qry(0, N-1, 1);
        }
        ret[pos] = i;
        upd(0, N-1, pos, pos, inf, 1);
        upd(0, N-1, pos-K+1, pos-1, -1, 1);
        if(pos-K+1<0) stk[++tp] = pos+N-K;
    }
//    for(int x: ret) cout << x << " ";
//    cout << endl;
    return ret;
}
void init(int k, vi r){
    r.insert(r.end(), r.begin(), r.end());
    N = r.size(); K = k;
    ord1 = solve(r);
    for(int &x: r) x = k-1-x;
    ord2 = solve(r);
}
int compare_plants(int x, int y){
    if(x > y) return -compare_plants(y, x);
    if(ord1[x] > ord1[y] || ord2[x+N/2] < ord2[y]) return -1;
    if(ord2[x] > ord2[y] || ord1[x+N/2] < ord1[y]) return 1;
    return 0;
}
//int main(){
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int k=3; vi a={0, 1, 1, 2};
//    init(k, a);
//    for(int i=0; i<a.size(); i++)
//        for(int j=i+1; j<a.size(); j++)
//            cout << i << " vs " << j << " = " << compare_plants(i, j) << endl;
//}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 66 ms 9464 KB Output is correct
7 Correct 131 ms 10072 KB Output is correct
8 Runtime error 144 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 11 ms 6656 KB Output is correct
7 Correct 93 ms 9720 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 9 ms 6656 KB Output is correct
10 Correct 91 ms 9592 KB Output is correct
11 Correct 86 ms 9468 KB Output is correct
12 Correct 88 ms 9720 KB Output is correct
13 Correct 91 ms 9592 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 11 ms 6656 KB Output is correct
7 Correct 93 ms 9720 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 9 ms 6656 KB Output is correct
10 Correct 91 ms 9592 KB Output is correct
11 Correct 86 ms 9468 KB Output is correct
12 Correct 88 ms 9720 KB Output is correct
13 Correct 91 ms 9592 KB Output is correct
14 Correct 184 ms 9944 KB Output is correct
15 Runtime error 189 ms 25960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 76 ms 9464 KB Output is correct
4 Runtime error 147 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 8 ms 6528 KB Output is correct
3 Correct 5 ms 6656 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 9 ms 6640 KB Output is correct
7 Correct 20 ms 7168 KB Output is correct
8 Correct 20 ms 7264 KB Output is correct
9 Correct 20 ms 7168 KB Output is correct
10 Correct 20 ms 7296 KB Output is correct
11 Correct 19 ms 7168 KB Output is correct
12 Correct 23 ms 7168 KB Output is correct
13 Correct 20 ms 7168 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Runtime error 134 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 66 ms 9464 KB Output is correct
7 Correct 131 ms 10072 KB Output is correct
8 Runtime error 144 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -