Submission #966844

#	Time	Username	Problem	Language	Result	Execution time	Memory
966844		anton	The Potion of Great Power (CEOI20_potion)	C++17	21 / 100	845 ms	262144 KiB

potion

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

struct Node{
    int subsz= 0, id = -1;
    int l = -1, r = -1;
    Node(){};
    Node(int i, int sz):subsz(sz), id(i){};
    
};
const int INF = 1e5;

vector<int> ids;
struct pSet{
    vector<pii> events;
    vector<Node> tree;

    pSet(){
        tree.reserve(500);
        tree.push_back(create(-1, -1));
        events.push_back({0, 0});
    }
    void set(int t, int id, int v){
        events.push_back({t, update(id, v, 0, INF, events.back().second)});
    }

    vector<int> get_inside_at(int t){
        int cur= 0;
        for(int step = (1<<18); step>=1; step/=2){
            if(cur+step<events.size()){
                if(events[cur+step].first<=t){
                    cur+=step;
                }
            }
        }
        get(0, INF, events[cur].second);
        
        vector<int> res;
        swap(res, ids);
        return res;
    }

    Node create(int lid, int rid){
        Node res;
        res.subsz = 0;
        res.l = lid;
        res.r = rid;
        if(res.l!=-1){
            res.subsz += tree[res.l].subsz;
        }
        if(res.r!=-1){
            res.subsz += tree[res.r].subsz;
        }
        return res;
    }

    int update(int id, int v, int lt, int rt, int t){
        Node res;
        if(lt==rt){
            res = Node(id, v);
        }
        else{
            int mid = (lt+rt)/2;
            int lid= -1, rid= -1;
            if(t!=-1){
                lid= tree[t].l;
                rid =tree[t].r;
            }
            if(id<=mid){
                res = create(update(id, v, lt, mid, lid), rid);
            }
            else{
                res = create(lid, update(id, v, mid+1, rt, rid));
            }
        }

        if(res.subsz>0|| (lt==0 && rt==INF)){
            tree.push_back(res);
            return tree.size()-1;
        }
        else{
            return -1;
        }
    }

    void get( int lt, int rt, int t){
        if(lt==rt){
            if(tree[t].subsz == 1){
                ids.push_back(tree[t].id);
            }
        }
        else{
            int mid =(lt+rt)/2;
            if(tree[t].l!=-1){
                get(lt, mid, tree[t].l);
            }
            if(tree[t].r!=-1){
                get(mid+1, rt, tree[t].r);
            }
        }
    }
};

vector<pSet> vs;
vector<int> h;
set<pii> cur;
vector<int> redir;
vector<int> order;
int n;

void init(int N, int D, int H[]) {
    
    vs.resize(N);
    
    h.resize(N);
    redir.resize(N);
    order.resize(N);
    for(int i = 0; i<N; i++){
        h[i] = H[i];
        order[i] = i;
    }


    auto cmp =[&](int a, int b){
        return h[a]<h[b];
    };
    sort(order.begin(),order.end(), cmp);
    sort(h.begin(), h.end());
    n= N;

    for(int i = 0; i<n; i++){
        redir[order[i]] = i;
    }
    
}
void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i<U; i++){
        int a= redir[A[i]], b= redir[B[i]];

        if(a>b){
            swap(a, b);
        }
        if((cur.find({a, b})!=cur.end())){
            cur.erase({a, b});
            vs[a].set(i+1, b, 0);
            vs[b].set(i+1, a, 0);
        }
        else{
            cur.insert({a, b});
            vs[a].set(i+1, b, 1);
            vs[b].set(i+1, a, 1);
        }
        
    }
}

int dist(vector<int>& a,  vector<int>& b){
    if(a.size() == 0 || b.size() == 0){
        return 1e9;
    }   
    int ia =0, ib = 0;

    int res= abs(a[0]-b[0]);
    while(ia<a.size()-1 || ib<b.size()-1){
        if(ia==a.size()-1){
            ib++;
        }
        else if(ib==b.size()-1){
            ia++;
        }
        else if(a[ia]<=b[ib]){
            ia++;
        }
        else{
            ib++;
        }

        res = min(res, abs(a[ia]-b[ib]));
    }
    return res;
}

int question(int x, int y, int v) {
    auto vx = vs[redir[x]].get_inside_at(v);
    for(int& e: vx){
        e = h[e];
    }
    auto vy = vs[redir[y]].get_inside_at(v);
    for(int& e: vy){
        e = h[e];
    }
    return dist(vx, vy);
}

Compilation message (stderr)

potion.cpp: In member function 'std::vector<int> pSet::get_inside_at(int)':
potion.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if(cur+step<events.size()){
      |                ~~~~~~~~^~~~~~~~~~~~~~
potion.cpp: In function 'int dist(std::vector<int>&, std::vector<int>&)':
potion.cpp:166:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(ia<a.size()-1 || ib<b.size()-1){
      |           ~~^~~~~~~~~~~
potion.cpp:166:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(ia<a.size()-1 || ib<b.size()-1){
      |                            ~~^~~~~~~~~~~
potion.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         if(ia==a.size()-1){
      |            ~~^~~~~~~~~~~~
potion.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         else if(ib==b.size()-1){
      |                 ~~^~~~~~~~~~~~

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