oj.uz

Submission #648820

# Submission time Handle Problem Language Result Execution time Memory
648820 2022-10-08T11:25:25 Z idas The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 82980 KB 
#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];

void init(int N, int D, int H[]) {
    n=N; d=D; FOR(i, 0, n) h[i]=H[i];

}

const int C=50;
vector<pii> ad[MxN];
vector<set<int>> con[MxN]; // con[i][j] - all adj for each N, Blk
set<int> cur[MxN]; //temporary adj set to get groups

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)
    {
        ad[a[i]].pb({i,b[i]});
        ad[b[i]].pb({i,a[i]});
    }

    FOR(i, 0, n)
    {
        FOR(j, 0, sz(ad[i]))
        {
            int x=ad[i][j].s;

            if(j%C==0){
                con[i].pb(cur[i]);
//                cur[i].clear();
            }
            if(cur[i].count(x)) cur[i].erase(x);
            else cur[i].insert(x);
        }
        con[i].pb(cur[i]);
    }
}

int question(int x, int y, int v) {
    if(sz(ad[x])==0||sz(ad[y])==0||v==0) return INF;

    auto it=upper_bound(all(ad[x]), pii({v-1,INF}));
    it=prev(it);

    int idx=it-ad[x].begin(); //idx of where last relevant pair is
    int blk=idx/C;

    set<int> arx;
    for(auto xx : con[x][blk]) arx.insert(xx);

    FOR(i, blk*C, idx+1)
    {
        int val=ad[x][i].s;
        if(arx.count(val)) arx.erase(val);
        else arx.insert(val);
    }

    it=upper_bound(all(ad[y]), pii({v-1,INF}));
    it=prev(it);

    idx=it-ad[y].begin();
    blk=idx/C;

    set<int> ary;
    for(auto xx : con[y][blk]) ary.insert(xx);

    FOR(i, blk*C, idx+1)
    {
        int val=ad[y][i].s;
        if(ary.count(val)) ary.erase(val);
        else ary.insert(val);
    }

    vi arr, brr;
    for(auto iter : arx) arr.pb(h[iter]);
    for(auto iter : ary) brr.pb(h[iter]);

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

/*
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14


5 100 4 5
2 1 2 3 3
0 3
1 3
1 4
4 2
3 4 0 1000000000
3 4 1 1000000000
3 4 2 1000000000
3 4 3 0
3 4 4 0
*/

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10064 KB Output is correct
2 Correct 7 ms 10064 KB Output is correct
3 Correct 7 ms 10064 KB Output is correct
4 Correct 33 ms 17104 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 68104 KB Output is correct
2 Correct 291 ms 68064 KB Output is correct
3 Correct 443 ms 27376 KB Output is correct
4 Execution timed out 3018 ms 82980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13168 KB Output is correct
2 Correct 233 ms 10960 KB Output is correct
3 Correct 457 ms 11032 KB Output is correct
4 Correct 2001 ms 13392 KB Output is correct
5 Correct 2008 ms 13776 KB Output is correct
6 Correct 223 ms 11984 KB Output is correct
7 Correct 1767 ms 12112 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 7 ms 10064 KB Output is correct
3 Correct 7 ms 10064 KB Output is correct
4 Correct 7 ms 10064 KB Output is correct
5 Correct 33 ms 17104 KB Output is correct
6 Correct 303 ms 68104 KB Output is correct
7 Correct 291 ms 68064 KB Output is correct
8 Correct 443 ms 27376 KB Output is correct
9 Execution timed out 3018 ms 82980 KB Time limit exceeded
10 Halted 0 ms 0 KB -