Submission #808744

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

potion

#include <bits/stdc++.h>

using namespace std;

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

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

constexpr int N = (int)1e5+1;

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();
        *nw = *v;
        nw->sum ^= 1;
        return nw;
    }
    int m = (l+r)>>1;
    if(v->l == nullptr) v->l = new node();
    if(v->r == nullptr) v->r = new node();
    node* nw = new node();
    *nw = *v;
    if(pos <= m){
        nw->l = upd(nw->l,l,m,pos);
    } else {
        nw->r = upd(nw->r,m+1,r,pos);
    }
    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[]) {
    for(int i = 0; i < n; i++){
        roots[i].push_back(new node());
        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>& vertexes){
    if(Sum(v) == 0) return;
    if(l == r){
        vertexes.push_back(l);
        return;
    }
    int m = (l+r)>>1;
    get(v->l,l,m,vertexes);
    get(v->r,m+1,r,vertexes);
    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> vertexes[2];
    get(root1,0,n-1,vertexes[0]);
    get(root2,0,n-1,vertexes[1]);
    vector<int> heights[2];
    // cerr << "vertexes " << x << ": ";
    // for(auto& v : vertexes[0]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    // cerr << "vertexes " << y << ": ";
    // for(auto& v : vertexes[1]){
    //     cerr << v << " ";
    // }
    // cerr << "\n";
    // cerr << "\n";
    for(int i = 0; i < 2; i++){
        for(auto& v : vertexes[i]){
            heights[i].push_back(H[v]);
        }
        sort(heights[i].begin(),heights[i].end());
        if(heights[i].empty())
            return (int)1e9;
    }
    int ans = abs(heights[0][0] - heights[1][0]);
    int j = 0;
    for(auto& h : heights[0]){
        while(j < heights[1].size() && heights[1][j] < h) j++;
        for(int i = max(0,j-2); i < min(j+2,(int)heights[1].size()); i++)
            ans = min(ans,abs(h-heights[1][i]));
    }
    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:137:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         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