oj.uz

Submission #308340

# Submission time Handle Problem Language Result Execution time Memory
308340 2020-10-01T00:35:40 Z bruce_test Comparing Plants (IOI20_plants) C++14
25 / 100
 168 ms 25848 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]; 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);
        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) upd(0, N-1, pos+N-K, N-1, -1, 1);
    }
//    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 6548 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 67 ms 9388 KB Output is correct
7 Correct 132 ms 10200 KB Output is correct
8 Runtime error 145 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 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 9 ms 6656 KB Output is correct
7 Correct 93 ms 9592 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 9 ms 6656 KB Output is correct
10 Correct 94 ms 9592 KB Output is correct
11 Correct 87 ms 9464 KB Output is correct
12 Correct 92 ms 9720 KB Output is correct
13 Correct 93 ms 9592 KB Output is correct

Subtask #3
0 / 13.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 9 ms 6656 KB Output is correct
7 Correct 93 ms 9592 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 9 ms 6656 KB Output is correct
10 Correct 94 ms 9592 KB Output is correct
11 Correct 87 ms 9464 KB Output is correct
12 Correct 92 ms 9720 KB Output is correct
13 Correct 93 ms 9592 KB Output is correct
14 Correct 168 ms 10072 KB Output is correct
15 Runtime error 168 ms 25848 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 6 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 81 ms 9464 KB Output is correct
4 Runtime error 146 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 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 7 ms 6656 KB Output is correct
7 Correct 21 ms 7296 KB Output is correct
8 Correct 21 ms 7168 KB Output is correct
9 Correct 20 ms 7168 KB Output is correct
10 Correct 22 ms 7160 KB Output is correct
11 Correct 20 ms 7168 KB Output is correct
12 Correct 21 ms 7168 KB Output is correct
13 Correct 21 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 6548 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 67 ms 9388 KB Output is correct
7 Correct 132 ms 10200 KB Output is correct
8 Runtime error 145 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -