oj.uz

Submission #645263

# Submission time Handle Problem Language Result Execution time Memory
645263 2022-09-26T15:05:16 Z idas The Potion of Great Power (CEOI20_potion) C++11
0 / 100
 193 ms 145148 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

const int MxN=1e5+10, MxU=2e5+10;
int n, d, u, h[MxN], a[MxU], b[MxU];

const int C=8000, SZ=26; //size of block, number of blocks
set<int> ad[SZ][MxN]; //adjacency list for each block

void init(int N, int D, int H[]) {
    n=N; d=D; FOR(i, 0, n) h[i]=H[i];
//    FOR(i, 0, SZ) FOR(j, 0, MxN) ad[i][j].clear();
}

void curseChanges(int U, int A[], int B[]) {
    u=U; FOR(i, 0, u) a[i]=A[i], b[i]=B[i];

    FOR(i, 0, u)
    {
        int blk=i/C; ++blk;
        if(ad[blk][a[i]].count(b[i])) ad[blk][a[i]].erase(b[i]);
        else ad[blk][a[i]].insert(b[i]);

        if(ad[blk][b[i]].count(a[i])) ad[blk][b[i]].erase(a[i]);
        else ad[blk][b[i]].insert(a[i]);
    }
}


int question(int x, int y, int v) {
    if(v==0) return INF;
    --v;

//    set<int> ar, br; //adjacency for x, y
//
//    int blk=v/C;
//    for(auto it : ad[blk][x]){
//        ar.insert(it);
//    }
//    for(auto it : ad[blk][y]){
//        br.insert(it);
//    }
//
//
//
//    int blk_end=blk*C;
//    FOR(i, blk_end, v+1)
//    {
//        if(a[i]==x){
//            if(ar.count(b[i])) ar.erase(b[i]);
//            else ar.insert(b[i]);
//        }
//        if(b[i]==x){
//            if(ar.count(a[i])) ar.erase(a[i]);
//            else ar.insert(a[i]);
//        }
//
//        if(a[i]==y){
//            if(br.count(b[i])) br.erase(b[i]);
//            else br.insert(b[i]);
//        }
//        if(b[i]==y){
//            if(br.count(a[i])) br.erase(a[i]);
//            else br.insert(a[i]);
//        }
//    }

    vi ar, br; //all adjacent to x, y
    int blk=v/C;
    for(auto it : ad[blk][x]){
        ar.pb(it);
    }
    for(auto it : ad[blk][y]){
        br.pb(it);
    }

    int blk_end=blk*C;
    FOR(i, blk_end, v+1)
    {
        if(a[i]==x){
            ar.pb(b[i]);
        }
        if(b[i]==x){
            ar.pb(a[i]);
        }
        if(a[i]==y){
            br.pb(b[i]);
        }
        if(b[i]==y){
            br.pb(a[i]);
        }
    }

    sort(all(ar)); sort(all(br));

    vi nwar;
    int val=-1, cn=0;
    for(auto it : ar){
        if(it!=val){
            if(val!=-1 && cn&1){
                nwar.pb(val);
            }
            val=it;
            cn=0;
        }
        cn++;
    }
    if(val!=-1 && cn&1){
        nwar.pb(val);
    }


    vi nwbr;
    val=-1; cn=0;
    for(auto it : br){
        if(it!=val){
            if(val!=-1 && cn&1){
                nwbr.pb(val);
            }
            val=it;
            cn=0;
        }
        cn++;
    }

    ar.swap(nwar); br.swap(nwbr);

    vi arr, brr;
    for(auto it : ar) arr.pb(h[it]);
    for(auto it : br) brr.pb(h[it]);

    sort(all(arr)); sort(all(brr));

    if(sz(arr)==0 || sz(brr)==0) return INF;

    int ret=INF;
    for(int i=0, j=0; i<sz(arr); i++){
        while(j+1<sz(brr) && abs(arr[i]-brr[j])>abs(arr[i]-brr[j+1])) j++;
        ret=min(ret, abs(arr[i]-brr[j]));
    }

    return ret;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122424 KB Output is correct
2 Incorrect 56 ms 122520 KB Incorrect
3 Halted 0 ms 0 KB -