oj.uz

Submission #1063171

# Submission time Handle Problem Language Result Execution time Memory
1063171 2024-08-17T14:49:49 Z new_acc Comparing Plants (IOI20_plants) C++14
5 / 100
 480 ms 93012 KB 
#include<bits/stdc++.h>
#include "plants.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=4e5+10;
const int SS=1<<19;
const int INFi=1e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,lazy[SS*2+10],k,li,t2[N],g[N],jp[N][L],jp2[N][L];
pair<int,int> seg[SS*2+10];
void push(int v){
    seg[v*2].fi+=lazy[v],seg[v*2+1].fi+=lazy[v];
    lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        lazy[v]+=x,seg[v].fi+=x;
        return;
    }
    int sr=(p+k)/2;
    push(v);
    upd(a,b,x,p,sr,v*2),upd(a,b,x,sr+1,k,v*2+1);
    if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
    else seg[v]=seg[v*2+1];
}
pair<int,int> qr(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return {INFi,-1};
    if(p>=a and k<=b) return seg[v];
    push(v);
    int sr=(p+k)/2;
    pair<int,int> q1=qr(a,b,p,sr,v*2),q2=qr(a,b,sr+1,k,v*2+1);
    if(q1.fi<q2.fi) return q1;
    return q2;
}
void build(int v){
    if(v>=SS){
        int id=v-SS;
        if(id>=1 and id<=n) seg[v]={t[id],id};
        else seg[v]={INFi,id};
    }else{
        build(v*2),build(v*2+1);
        if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
        else seg[v]=seg[v*2+1];
    }
}
void zn(int a){
    if(a>=k){
        pair<int,int> xd=qr(a-k+1,a-1);
        while(xd.fi==0){
            zn(xd.se);
            xd=qr(a-k+1,a-1);
        }
        t2[a]=--li;
    }else{
        pair<int,int> xd=qr(1,a-1);
        if(xd.fi!=0) xd=qr(n-(k-a)+1,n);
        while(xd.fi==0){
            zn(xd.se);
            xd=qr(1,a-1);
            if(xd.fi!=0) xd=qr(n-(k-a)+1,n);
        }
        t2[a]=--li;
    }
    if(a>=k) upd(a-k+1,a-1,-1);
    else{
        upd(1,a-1,-1);
        upd(n-(k-a)+1,n,-1);
    }
    upd(a,a,INFi);
}
void init(int kk,vi r){
    k=kk;
    n=r.size();
    for(int i=1;i<=n;i++) t[i]=r[i-1];
    build(1);
    li=n+1;
    pair<int,int> curr=qr(1,n);
    while(curr.fi==0){
        zn(curr.se);
        curr=qr(1,n);
    }
    for(int i=n+1;i<=n*2;i++) t2[i]=t2[i-n];        
    for(int i=1;i<=n;i++) g[t2[i]]=i;
    n*=2;
    for(int i=1;i<=n;i++) t[i]=INFi;
    build(1);
    n/=2;
    for(int i=n;i>=1;i--){
        upd(g[i],g[i],-INFi+i); 
        upd(g[i]+n,g[i]+n,-INFi+i); 
        pair<int,int> xd=qr(g[i]+1,g[i]+k-1);
        if(xd.fi>=INFi) jp[g[i]][0]=g[i],jp[g[i]+n][0]=n+g[i];
        else{
            jp[g[i]][0]=xd.se;
            if(xd.se<=n) jp[g[i]+n][0]=xd.se+n;
            else jp[g[i]+n][0]=g[i]+n;
        }
        xd=qr(g[i]+n-k+1,g[i]+n-1);
        if(xd.fi>=INFi) jp2[g[i]][0]=g[i],jp2[g[i]+n][0]=n+g[i];
        else{
            jp2[g[i]+n][0]=xd.se;
            if(xd.se>n) jp2[g[i]][0]=xd.se-n;
            else jp2[g[i]][0]=g[i];
        }
    }
    //for(int i=1;i<=n;i++) cout<<jp[i][0]<<" ";
    //cout<<"\n";
    for(int i2=1;i2<L;i2++){
        for(int i=1;i<=n*2;i++){
            jp[i][i2]=jp[jp[i][i2-1]][i2-1];
            jp2[i][i2]=jp2[jp2[i][i2-1]][i2-1];
        }
    }
}
int compare_plants(int x,int y){
    x++,y++;
    int curr=x; 
    for(int i=L-1;i>=0;i--)
        if(jp[curr][i]<=y) curr=jp[curr][i];
    int curr2=y;
    for(int i=L-1;i>=0;i--)
        if(jp[curr2][i]<=x+n) curr2=jp[curr2][i];
    if(t2[curr]<=t2[y] and y-curr<k) return -1;
    if(t2[curr2]<=t2[x+n] and x+n-curr2<k) return 1;
    curr=y; 
    for(int i=L-1;i>=0;i--){
        if(jp2[curr][i]>=x) curr=jp2[curr][i];
    }
    curr2=x+n;
    for(int i=L-1;i>=0;i--){
        if(jp2[curr2][i]>=y) curr2=jp2[curr2][i];
    }
    if(t2[curr]<=t2[x] and curr-x<k) return 1;
    if(t2[curr2]<=t2[y] and curr2-y<k) return -1;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19088 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 58 ms 22868 KB Output is correct
7 Correct 105 ms 30388 KB Output is correct
8 Correct 460 ms 86812 KB Output is correct
9 Correct 445 ms 86868 KB Output is correct
10 Correct 480 ms 86960 KB Output is correct
11 Correct 465 ms 87888 KB Output is correct
12 Correct 446 ms 90200 KB Output is correct
13 Correct 479 ms 93012 KB Output is correct
14 Correct 450 ms 86868 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 7 ms 19080 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 8 ms 19056 KB Output is correct
5 Incorrect 8 ms 19032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 7 ms 19080 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 8 ms 19056 KB Output is correct
5 Incorrect 8 ms 19032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Incorrect 70 ms 25712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 8 ms 19008 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Incorrect 10 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19288 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 18892 KB Output is correct
4 Incorrect 7 ms 19032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19088 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 58 ms 22868 KB Output is correct
7 Correct 105 ms 30388 KB Output is correct
8 Correct 460 ms 86812 KB Output is correct
9 Correct 445 ms 86868 KB Output is correct
10 Correct 480 ms 86960 KB Output is correct
11 Correct 465 ms 87888 KB Output is correct
12 Correct 446 ms 90200 KB Output is correct
13 Correct 479 ms 93012 KB Output is correct
14 Correct 450 ms 86868 KB Output is correct
15 Correct 8 ms 19032 KB Output is correct
16 Correct 7 ms 19080 KB Output is correct
17 Correct 7 ms 19036 KB Output is correct
18 Correct 8 ms 19056 KB Output is correct
19 Incorrect 8 ms 19032 KB Output isn't correct
20 Halted 0 ms 0 KB -