oj.uz

Submission #808651

# Submission time Handle Problem Language Result Execution time Memory
808651 2023-08-05T08:37:27 Z DJeniUp The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 418 ms 235172 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long 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[40*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;
    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]];
        p[A[i]].pb({i,h1});
        Add(h1,p[A[i]][p[A[i]].size()-2].sc,0,n-1,B[i]);

        h1++;
        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){
    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;
    }
    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]));

    }
    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]));

    }
    return res;
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2668 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3280 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 418 ms 235172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 350 ms 235148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 11224 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2668 KB Incorrect
2 Halted 0 ms 0 KB -