oj.uz

Submission #397666

# Submission time Handle Problem Language Result Execution time Memory
397666 2021-05-02T19:10:08 Z Antekb Comparing Plants (IOI20_plants) C++14
11 / 100
 4000 ms 2097156 KB 
#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int lazy[2*N];
pair<int, int> maks[2*N];
void prop1(int v){
    if(!lazy[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy[l]+=lazy[v];
    lazy[r]+=lazy[v];
    maks[l].st+=lazy[v];
    maks[r].st+=lazy[v];
    lazy[v]=0;
}
void add(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"a"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<v<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
    if(l==L && r==R){
        lazy[v]+=c;
        maks[v].st+=c;
        return;
    }
    prop1(v);
    int M=(L+R)>>1;
    if(l<=M)add(2*v, l, min(M, r), L, M, c);
    if(r>M)add(2*v+1, max(M+1, l), r, M+1, R, c);
    maks[v]=max(maks[2*v], maks[2*v+1]);
    return;
}
pair<int, int> quer1(int v, int l, int r, int L, int R){
    if(l==L && r==R){
        return maks[v];
    }
    int M=(L+R)>>1;
    prop1(v);
    pair<int, int> ans=mp(0, 0);
    if(l<=M)ans=max(ans, quer1(2*v, l, min(M, r), L, M));
    if(r>M)ans=max(ans, quer1(2*v+1, max(M+1, l), r, M+1, R));
    return ans;
}
int lazy2[2*N];
pair<int, int> ma[2*N];
void prop2(int v){
    if(!lazy2[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy2[l]+=lazy2[v];
    lazy2[r]+=lazy2[v];
    ma[l].st+=lazy2[v];
    ma[r].st+=lazy2[v];
    lazy2[v]=0;
}
void add2(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"b"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<"c"<<"\n";
    if(l==L && r==R){
        lazy2[v]+=c;
        ma[v].st+=c;
        return;
    }
    prop2(v);
    int M=(L+R)>>1;
    if(l<=M)add2(2*v, l, min(M, r), L, M, c);
    if(r>M)add2(2*v+1, max(M+1, l), r, M+1, R, c);
    ma[v]=max(ma[2*v], ma[2*v+1]);
    return;
}
pair<int, int> quer2(int v, int l, int r, int L, int R){
    if(l==L && r==R){
        return ma[v];
    }
    int M=(L+R)>>1;
    prop2(v);
    pair<int, int> ans=mp(0, 0);
    if(l<=M)ans=max(ans, quer2(2*v, l, min(M, r), L, M));
    if(r>M)ans=max(ans, quer2(2*v+1, max(M+1, l), r, M+1, R));
    return ans;
}
void check(int k, int n){
    while(maks[1].st==k){
        //cout<<"b\n";
        int v=1;
        while(v<N){
            prop1(v);
            if(maks[2*v].st==k)v*=2;
            else v=2*v+1;
        }
        add(1, v-N, v-N, 0, N-1, -N);
        add2(1, v-N, v-N, 0, N-1, N);
        if(v-N<n-1)add2(1, v-N+1, min(v-N+k, n-1), 0, N-1, -1);
        if(v-N+k>=n)add2(1, 0, v-N+k-n, 0, N-1, -1);
    }
}
vector<int> V, V2;
struct node{
    node* l=nullptr, *r=nullptr;
    int sum;
    void upd(){
        sum=0;
        if(l)sum+=l->sum;
        if(r)sum+=r->sum;
    }
    node(node* _l, node* _r) : l(_l), r(_r) {sum=1;}
};
node* left(node* v){if(!v)return nullptr; return v->l;}
node* right(node* v){if(!v)return nullptr; return v->r;}
node* add(node* v, int L, int R, int id){
    if(L==R){
        return new node(0, 0);
    }
    int M=(L+R)>>1;
    node* u=new node(left(v), right(v));
    if(id<=M)u->l=add(left(v), L, M, id);
    else u->r=add(right(v), M+1, R, id);
    u->upd();
    return u;
}
node* merge(node* u, node* v){
    if(!u)return v;
    if(!v)return u;
    node* w=new node(merge(left(u), left(v)), merge(right(u), right(v)));
    w->upd();
    return w;
}
bool czy(node* v, int L, int R, int id){
    if(!v)return 0;
    if(L==R)return 1;
    int M=(L+R)>>1;
    if(id<=M)return czy(left(v), L, M, id);
    else return czy(right(v), M+1, R, id);
}
vector<node* > b;
int n;
void addbit(int l, int r, node* c){
    r++;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1)b[l]=merge(b[l], c), l++;
        if(r&1)r--, b[r]=merge(b[r], c);
    }
}
void comp(int x){
    if(x==1)return;
    comp(x/2);
    b[x]=merge(b[x/2], b[x]);
}
vector<node*> ans;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void init(int k, std::vector<int> r) {
    /*b.clear();
    ans.clear();
    V.clear();
    for(int i=0; i<2*N; i++)maks[i]=ma[i]=mp(0, 0), lazy[i]=lazy2[i]=0;
    vector<int> perm(r.size());
    iota(perm.begin(), perm.end(), 0);
    shuffle(perm.begin(), perm.end(), rng);
    for(int i=0; i<r.size(); i++){
        cout<<perm[i];
        r[i]=0;
        for(int j=1; j<k; j++){
            r[i]+=(perm[i]>perm[(i+j)%r.size()]);
        }
    }
    cout<<"\n";
    for(int i=0; i<r.size(); i++)cout<<r[i]<<" ";
        cout<<"\n";*/
    n=r.size();
    k--;
    V.resize(n);
    for(int i=0; i<n; i++){
        ma[N+i].nd=-i;
        maks[N+i].st=r[i];
        maks[N+i].nd=-i;
    }
    for(int i=N-1; i>0; i--){
        ma[i]=max(ma[2*i], ma[2*i+1]);
        maks[i]=max(maks[2*i], maks[2*i+1]);
    }
    vector<int> S;
    b.resize(2*n);
    ans.resize(n);
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
    	while(ma[1].st==N){
            S.push_back(-ma[1].nd);
            add2(1, -ma[1].nd, -ma[1].nd, 0, N-1, -N);
            //cout<<"+";
        }
        int j=S[i];
        //cout<<j<<"\n";
        comp(j+n);
    	V[j]=i;
        b[j+n]=add(b[j+n], 0, N-1, j);
        ans[j]=b[j+n];
        //assert(ans[j]->sum==i+1);
        //for(int l=0; l<n; l++)cout<<ans[j][l];cout<<"\n";
        pair<int, int> u=mp(0,0);
        if(j<n-1){
            add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
            addbit(j+1, min(j+k, n-1), ans[j]);
            //u=max(u, quer2(1, j+1, min(j+k, n-1), 0, N-1));
        }
        if(j+k>=n){
            add2(1, 0, j+k-n, 0, N-1, 1);
            addbit(0, j+k-n, ans[j]);
            //u=max(u, quer2(1, 0, j+k-n, 0, N-1));
        }
        /*if(u.st==N){
            b[-u.nd]|=b[j];
            cout<<-u.nd<<"x\n";
        }*/
        u=mp(0, 0);
    	if(j){
            add(1, max(j-k, 0), j-1, 0, N-1, 1);
            addbit(max(j-k, 0), j-1, ans[j]);
            //u=max(u, quer1(1, max(j-k, 0), j-1, 0, N-1));
        }
        if(j-k<0){
            add(1, n+j-k, n-1, 0, N-1, 1);
            addbit(n+j-k, n-1, ans[j]);
            //u=max(u, quer1(1, n+j-k, n-1, 0, N-1));
        }
        /*if(u.st==k){
            b[-u.nd]|=b[j];
            cout<<-u.nd<<"y\n";
        }*/
    }
    return;
}
int compare_plants(int x, int y){
	if(czy(ans[x], 0, N-1, y))return 1;
	if(czy(ans[y], 0, N-1, x))return -1;
   	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4392 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 4 ms 4428 KB Output is correct
6 Correct 81 ms 8132 KB Output is correct
7 Correct 557 ms 175584 KB Output is correct
8 Correct 1561 ms 374412 KB Output is correct
9 Execution timed out 4078 ms 961584 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4428 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 18 ms 12492 KB Output is correct
6 Correct 2505 ms 1230200 KB Output is correct
7 Execution timed out 4208 ms 1890724 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4428 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 18 ms 12492 KB Output is correct
6 Correct 2505 ms 1230200 KB Output is correct
7 Execution timed out 4208 ms 1890724 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Correct 1469 ms 694616 KB Output is correct
4 Execution timed out 4053 ms 2097156 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4432 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 5 ms 4428 KB Output is correct
5 Correct 4 ms 4428 KB Output is correct
6 Correct 7 ms 5068 KB Output is correct
7 Correct 34 ms 11112 KB Output is correct
8 Correct 147 ms 69572 KB Output is correct
9 Correct 57 ms 23328 KB Output is correct
10 Correct 149 ms 71872 KB Output is correct
11 Correct 35 ms 12672 KB Output is correct
12 Correct 57 ms 25284 KB Output is correct
13 Correct 203 ms 107076 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4348 KB Output is correct
2 Correct 4 ms 4428 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 1428 ms 649196 KB Output is correct
6 Execution timed out 4202 ms 1947888 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 4 ms 4392 KB Output is correct
3 Correct 4 ms 4428 KB Output is correct
4 Correct 4 ms 4428 KB Output is correct
5 Correct 4 ms 4428 KB Output is correct
6 Correct 81 ms 8132 KB Output is correct
7 Correct 557 ms 175584 KB Output is correct
8 Correct 1561 ms 374412 KB Output is correct
9 Execution timed out 4078 ms 961584 KB Time limit exceeded
10 Halted 0 ms 0 KB -