Submission #808788

#	Time	Username	Problem	Language	Result	Execution time	Memory
808788		welleyth	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3073 ms	239732 KiB

potion

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

struct node{
    node *l,*r;
    bool sum;
    node(){
        l = r = nullptr;
        sum = 0;
    }
    void recalc(){
        sum = false;
        if(l)
            sum |= l->sum;
        if(r)
            sum |= r->sum;
    }
};

inline bool Sum(node* v){
    return v ? v->sum : 0;
}

constexpr int N = (int)1e5;

vector<node*> roots[N];
vector<int> times[N];

node* upd(node* v,int l,int r,int pos){
    if(l == r){
        node* nw = new node();
        if(v)
            *nw = *v;
        nw->sum ^= 1;
        return nw;
    }
    int m = (l+r)>>1;
    node* nw = new node();
    if(v)
        *nw = *v;
    if(pos <= m){
        nw->l = upd(nw->l,l,m,pos);
        if(Sum(nw->l) == 0){
            delete nw->l;
            nw->l = nullptr;
        }
    } else {
        nw->r = upd(nw->r,m+1,r,pos);
        if(Sum(nw->r) == 0){
            delete nw->r;
            nw->r = nullptr;
        }
    }
    nw->recalc();
    return nw;
}

int H[N];
int n;
int D;

void init(int N, int D, int H[]) {
    ::D = D;
    for(int i = 0; i < N; i++){
        ::H[i] = H[i];
    }
    ::n = N;
    return;
}

void curseChanges(int U, int A[], int B[]) {
    node* root = new node();
    for(int i = 0; i < n; i++){
        roots[i].push_back(root);
        times[i].push_back(0);
    }
    for(int i = 0; i < U; i++){
        int a = A[i], b = B[i];
        int tm = i+1;
        roots[a].push_back(upd(roots[a].back(),0,n-1,b));
        times[a].push_back(tm);
        // cerr << "adding " << tm << " to " << a << " and " << b << "\n";
        roots[b].push_back(upd(roots[b].back(),0,n-1,a));
        times[b].push_back(tm);
    }
    return;
}

void get(node* v,int l,int r,vector<int>& heights){
    if(Sum(v) == 0) return;
    if(l == r){
        heights.push_back(H[l]);
        return;
    }
    int m = (l+r)>>1;
    get(v->l,l,m,heights);
    get(v->r,m+1,r,heights);
    return;
}

int question(int x, int y, int v) {
    // cerr << "x,y,v: " << x << " " << y << " " << v << "\n";
    // cerr << "times " << x << ": ";
    // for(auto& v : times[x]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    // cerr << "times " << y << ": ";
    // for(auto& v : times[y]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    int pos1 = upper_bound(times[x].begin(),times[x].end(),v) - times[x].begin() - 1;
    int pos2 = upper_bound(times[y].begin(),times[y].end(),v) - times[y].begin() - 1;
    // cerr << "pos1: " << pos1 << "\n";
    // cerr << "pos2: " << pos2 << "\n";
    node* root1 = roots[x][pos1];
    node* root2 = roots[y][pos2];
    vector<int> heights[2];
    get(root1,0,n-1,heights[0]);
    get(root2,0,n-1,heights[1]);
    sort(heights[0].begin(),heights[0].end());
    sort(heights[1].begin(),heights[1].end());
    int ans = (int)1e9;
    int j = 0;
    for(auto& h : heights[0]){
        while(j < heights[1].size() && heights[1][j] < h) j++;
        for(int i = max(0,j-1); i < min(j+1,(int)heights[1].size()); i++)
            ans = min(ans,abs(h-heights[1][i]));
    }
    // cerr << "ans: " << ans << "\n";
    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         while(j < heights[1].size() && heights[1][j] < h) j++;
      |               ~~^~~~~~~~~~~~~~~~~~~

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