oj.uz

Submission #808658

# Submission time Handle Problem Language Result Execution time Memory
808658 2023-08-05T08:51:47 Z DJeniUp The Potion of Great Power (CEOI20_potion) C++17
35 / 100
 3000 ms 101320 KB 
#include "bits/stdc++.h"
using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;

#define N1 100007
#define INF 1000000000
#define pb push_back
#define fr first
#define sc second

ll n,m,h[N1],h1;

vector<pairll>p[N1];

map<ll,ll>mp;

struct T{
    ll l,r,s;
}t[80*N1];

struct D{
    ll n,h;
}d[N1];

bool mcp(D d1,D d2){
    return d1.h<d2.h;
}

void init(int N, int D, int H[]) {
    n=N;
    m=D;
    for(int i=0;i<n;i++){
        h[i]=H[i];
        p[i].pb({0,0});
        d[i]={i,h[i]};
    }

    sort(d,d+n,mcp);
    sort(h,h+n);
    for(int i=0;i<n;i++){
        mp[d[i].n]=i;
    }
    return ;
}

void Add(ll x,ll y,ll l,ll r,ll tl){

    if(r<tl || tl<l)return ;
    if(l==r){
        t[x].s^=1;
        return ;
    }
    ll m1=(l+r)/2;
    if(tl<=m1){
        h1++;
        t[h1]=t[t[y].l];
        t[x].l=h1;
        Add(t[x].l,t[y].l,l,m1,tl);
    }else{
        h1++;
        t[h1]=t[t[y].r];
        t[x].r=h1;
        Add(t[x].r,t[y].r,m1+1,r,tl);
    }
    t[x].s=t[t[x].l].s+t[t[x].r].s;
   // cout<<"?! "<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<t[x].s<<endl;
    return ;
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=0;i<U;i++){
        h1++;
        A[i]=mp[A[i]];
        B[i]=mp[B[i]];
        t[h1]=t[p[A[i]].back().sc];
        p[A[i]].pb({i,h1});
        Add(h1,p[A[i]][p[A[i]].size()-2].sc,0,n-1,B[i]);

        h1++;
        t[h1]=t[p[B[i]].back().sc];
        p[B[i]].pb({i,h1});
        Add(h1,p[B[i]][p[B[i]].size()-2].sc,0,n-1,A[i]);
    }
    return ;
}

ll R(ll x,ll l,ll r,ll tl){
    //cout<<"? "<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<t[x].s<<endl;
    if(r<tl || t[x].s==0)return INF;
    if(l==r)return l;
    ll m1=(l+r)/2;
    ll r1=R(t[x].l,l,m1,tl);
    if(r1!=INF)return r1;
    return R(t[x].r,m1+1,r,tl);
}

int question(int x, int y, int v) {
    x=mp[x];
    y=mp[y];
    ll res=INF;
    ll l=0;
    ll r=p[x].size()-1;
    while(l<r){
        ll m1=(l+r+1)/2;
        if(p[x][m1].fr>=v)r=m1-1;
        else l=m1;
    }

    ll l1=0;
    ll r1=p[y].size()-1;
    while(l1<r1){
        ll m1=(l1+r1+1)/2;
        if(p[y][m1].fr>=v)r1=m1-1;
        else l1=m1;
    }
    //cout<<"! "<<l<<" "<<l1<<endl;
    ll a=-1;
    while(1){
        a=R(p[x][l].sc,0,n-1,a+1);
        if(a==INF)break;
        ll b=R(p[y][l1].sc,0,n-1,a);
        if(b==INF)break;
        res=min(res,abs(h[a]-h[b]));
        if(res==0)break;
        //cout<<a<<" "<<b<<endl;
    }
    a=-1;
    while(1){
        a=R(p[y][l1].sc,0,n-1,a+1);
        if(a==INF)break;
        ll b=R(p[x][l].sc,0,n-1,a);
        if(b==INF)break;
        res=min(res,abs(h[a]-h[b]));
        if(res==0)break;
        //cout<<a<<" "<<b<<endl;

    }
    return res;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3024 KB Output is correct
2 Correct 3 ms 3024 KB Output is correct
3 Correct 3 ms 3024 KB Output is correct
4 Correct 61 ms 12360 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 101296 KB Output is correct
2 Correct 691 ms 101320 KB Output is correct
3 Correct 510 ms 100680 KB Output is correct
4 Execution timed out 3070 ms 60324 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 101244 KB Output is correct
2 Correct 404 ms 101152 KB Output is correct
3 Correct 661 ms 100540 KB Output is correct
4 Correct 668 ms 100820 KB Output is correct
5 Correct 521 ms 101224 KB Output is correct
6 Correct 641 ms 100608 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7248 KB Output is correct
2 Correct 198 ms 7220 KB Output is correct
3 Correct 440 ms 7248 KB Output is correct
4 Execution timed out 3075 ms 7248 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 4 ms 3024 KB Output is correct
3 Correct 3 ms 3024 KB Output is correct
4 Correct 3 ms 3024 KB Output is correct
5 Correct 61 ms 12360 KB Output is correct
6 Correct 685 ms 101296 KB Output is correct
7 Correct 691 ms 101320 KB Output is correct
8 Correct 510 ms 100680 KB Output is correct
9 Execution timed out 3070 ms 60324 KB Time limit exceeded
10 Halted 0 ms 0 KB -