oj.uz

Submission #308341

# Submission time Handle Problem Language Result Execution time Memory
308341 2020-10-01T00:43:49 Z bruce_test Comparing Plants (IOI20_plants) C++11
25 / 100
 173 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]; 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 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 67 ms 9464 KB Output is correct
7 Correct 128 ms 9816 KB Output is correct
8 Runtime error 146 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 6 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 95 ms 9592 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 10 ms 6656 KB Output is correct
10 Correct 94 ms 9592 KB Output is correct
11 Correct 92 ms 9464 KB Output is correct
12 Correct 87 ms 9720 KB Output is correct
13 Correct 94 ms 9624 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 6 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 95 ms 9592 KB Output is correct
8 Correct 7 ms 6656 KB Output is correct
9 Correct 10 ms 6656 KB Output is correct
10 Correct 94 ms 9592 KB Output is correct
11 Correct 92 ms 9464 KB Output is correct
12 Correct 87 ms 9720 KB Output is correct
13 Correct 94 ms 9624 KB Output is correct
14 Correct 165 ms 9952 KB Output is correct
15 Runtime error 173 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 82 ms 9464 KB Output is correct
4 Runtime error 152 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 20 ms 7168 KB Output is correct
8 Correct 21 ms 7168 KB Output is correct
9 Correct 20 ms 7168 KB Output is correct
10 Correct 21 ms 7168 KB Output is correct
11 Correct 20 ms 7168 KB Output is correct
12 Correct 22 ms 7168 KB Output is correct
13 Correct 20 ms 7188 KB Output is correct

Subtask #6
0 / 15.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 6 ms 6656 KB Output is correct
5 Correct 8 ms 6656 KB Output is correct
6 Runtime error 132 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 67 ms 9464 KB Output is correct
7 Correct 128 ms 9816 KB Output is correct
8 Runtime error 146 ms 25832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -