Submission #660709

#	Time	Username	Problem	Language	Result	Execution time	Memory
660709		Lobo	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	3040 ms	34160 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define ll long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, a[maxn], idord[maxn];
vector<pair<int,int>> ord;

vector<pair<int,int>> g[maxn];
vector<int> frds[maxn];
int tr[10*maxn], cntno, stno[maxn], lc[10*maxn], rc[10*maxn];

int build(int no, int l, int r) {
    if(no == 0) no = ++cntno;
    tr[no] = inf1;
    if(l == r) return no;
    int mid=(l+r)>>1;
    lc[no] = build(lc[no],l,mid);
    rc[no] = build(rc[no],mid+1,r);
    return no;
}

int upd(int no, int l, int r, int pos) {
    if(no == 0) no = ++cntno;
    if(l == r) {
        if(tr[no] == inf1) tr[no] = pos;
        else tr[no] = inf1;
        return no;
    }
    int mid=(l+r)>>1;
    if(pos <= mid) {
        lc[no] = upd(lc[no],l,mid,pos);
    }
    else {
        rc[no] = upd(rc[no],mid+1,r,pos);
    }

    tr[no] = min(tr[lc[no]],tr[rc[no]]);
    return no;
}

int qry(int no, int l, int r, int L, int R) {
    if(L > R) return inf1;
    if(no == 0 || l > R || r < L) return inf1;
    if(l >= L && r <= R) {
        return tr[no];
    }
    int mid=(l+r)>>1;
    return min(qry(lc[no],l,mid,L,R),qry(rc[no],mid+1,r,L,R));
}

void init(int N, int D, int H[]) {
    n = N;
    for(int i = 0; i < n; i++) {
        ord.pb(mp(H[i],i));
    }
    sort(all(ord));
    for(int i = 0; i < n; i++) {
        idord[ord[i].sc] = i;
        a[i] = ord[i].fr;
    }
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; i++) {
        int u = idord[A[i]];
        int v = idord[B[i]];

        g[u].pb(mp(i+1,v));
        g[v].pb(mp(i+1,u));
    }

    tr[0] = inf1;
    for(int i = 0; i < n; i++) {
        frds[i].pb(i);
        for(auto X : g[i]) {
            int j = X.sc;
            frds[i].pb(j);
        }
        sort(all(frds[i]));
        frds[i].erase(unique(all(frds[i])),frds[i].end());
        // To get in which id v is, I can do lower_bound(v)-begin

        stno[i] = ++cntno;
        build(stno[i],0,(int) frds[i].size()-1);
        upd(stno[i],0,(int) frds[i].size()-1, lower_bound(all(frds[i]),i)-frds[i].begin());
        upd(stno[i],0,(int) frds[i].size()-1, lower_bound(all(frds[i]),i)-frds[i].begin());

        for(auto X : g[i]) {
            int id = X.fr;
            int j = X.sc;
            upd(stno[i],0,(int) frds[i].size()-1,lower_bound(all(frds[i]),j)-frds[i].begin());
        }
        // cout << lower_bound(all(frds[i]),i)-frds[i].begin() << " " << tr[stno[i]] << endl;
    }
}

int question(int x, int y, int v) {
    x = idord[x];
    y = idord[y];
    int nox = stno[x];
    int noy = stno[y];

    int i = qry(nox,0,(int) frds[x].size()-1,0,(int) frds[x].size()-1);
    int j = qry(noy,0,(int) frds[y].size()-1,0,(int) frds[y].size()-1);

    if(i == inf1) return 1000000000;
    if(j == inf1) return 1000000000;

    int ans = inf1;
    while(i != inf1 && j != inf1) {
        ans = min(ans, abs(a[frds[x][i]]-a[frds[y][j]]));
        if(a[frds[x][i]] < a[frds[y][j]]) {
            //increase i
            i = qry(nox,0,(int) frds[x].size()-1,i+1,(int) frds[x].size() -1);
        }
        else {
            j = qry(noy,0,(int) frds[y].size()-1,j+1,(int) frds[y].size() -1);
        }
    }

    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:101:17: warning: unused variable 'id' [-Wunused-variable]
  101 |             int id = X.fr;
      |                 ^~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30