Submission #966879

#	Time	Username	Problem	Language	Result	Execution time	Memory
966879		anton	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	720 ms	72108 KiB

potion

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
typedef complex<int> point;

const int INF = 1e9;

int dist(vector<int>& a,  vector<int>& b){
    if(a.size() == 0 || b.size() == 0){
        return INF;
    }   
    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;
}

struct Event{
    int date;
    vector<int> list;
    int change;
    Event(int t,int v): date(t), change(v){};
    Event(int t, vector<int> v): date(t){
        list =v;
    };
};

vector<int> apply(vector<int>& a, vector<int>&ev){
    sort(ev.begin(), ev.end());
    
    vector<int> res;

    auto add =[&](int v){
        if(res.size()>0 && res.back() == v){
            res.pop_back();
        }
        else{
            res.push_back(v);
        }
    };
    int aid = 0;
    int eid = 0;
    while(aid<a.size() || eid<ev.size()){
        
        if(eid>=ev.size()){
            add(a[aid]);
            aid++;
        }
        else if(aid>=a.size()){
            add(ev[eid]);
            eid++;
        }
        else{ 
            if(a[aid]<=ev[eid]){
                add(a[aid]);
                aid++;
            }
            else{
                add(ev[eid]);
                eid++;
            } 

        }
    }
    return res;
}
vector<vector<int>> vs;
vector<int> h;
set<pii> cur;

vector<vector<Event>> events;
vector<vector<int>> backed_up;
vector<int> order;
vector<int> redir;
int n;
const int TR = 10;

void init(int N, int D, int H[]) {
    
    n = N;
    vs.resize(N);
    h.resize(N);
    events.resize(N);
    backed_up.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());

    for(int i = 0; i<n; i++){
        redir[order[i]] = i;
    }
}


void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i<n; i++){
        events[i].push_back(Event(0, vector<int>()));
    }

    auto p_event = [&](int id,int t, int ev){
        backed_up[id].push_back(ev);
        if(backed_up[id].size()==TR){
            events[id].push_back(Event(t, apply(events[id][events[id].size()-TR].list,backed_up[id])));
            backed_up[id].clear();
        }
        else{
            events[id].push_back(Event(t, ev));
        }
    };
    for(int i = 0; i<U; i++){
        int a= redir[A[i]], b= redir[B[i]];
        if(cur.find({a, b})!=cur.end()){
            cur.erase({a, b});
        }
        else if(cur.find({b, a})!=cur.end()){
            cur.erase({b, a});
        }
        else{
            cur.insert({a, b});
        }
        p_event(a, i+1, b);
        p_event(b, i+1, a);
    }
}

int get_last(int id, int t){
    int cur=  0;
    for(int step = (1<<18); step>=1; step/=2){
        if(cur+step<events[id].size()){
            if(events[id][cur+step].date<=t){
                cur+=step;
            }
        }
    }
    return cur;
}
vector<int> reconstruct(int id, int eid){
    Event base = events[id][(eid/TR) * TR];
    vector<int> others;
    for(int i = 1; i<=eid%TR; i++){
        others.push_back(events[id][(eid/TR) * TR + i].change);
    }
    return apply(base.list, others);
}
int question(int x, int y, int v) {
    x= redir[x];
    y= redir[y];
    auto xm =reconstruct(x, get_last(x, v));
    auto ym = reconstruct(y, get_last(y, v));
    
    for(int& e: xm){
        e= h[e];
    }
    for(int& e: ym){
        e= h[e];
    }
    return dist(xm, ym);
}
/*
int H[1000*1000];
int A[1000*1000];
int B[1000*1000];
signed main(){
    int N, D, U, Q;
    std::cin >> N >> D >> U >> Q;
    for(int i = 0; i<N; i++){
        cin>>H[i];
    }
    init(N, D, H);
    for(int i = 0; i<U; i++){
        cin>>A[i];
        cin>>B[i];
    }
    curseChanges(U, A, B);
    for(int i=  0; i<Q; i++){
        int a, b, v;
        cin>>a>>b>>v;
        cout<<question(a, b, v)<<endl;
    }
}
*/

Compilation message (stderr)

potion.cpp: In function 'int dist(std::vector<int>&, std::vector<int>&)':
potion.cpp:17:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(ia<a.size()-1 || ib<b.size()-1){
      |           ~~^~~~~~~~~~~
potion.cpp:17:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(ia<a.size()-1 || ib<b.size()-1){
      |                            ~~^~~~~~~~~~~
potion.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(ia==a.size()-1){
      |            ~~^~~~~~~~~~~~
potion.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         else if(ib==b.size()-1){
      |                 ~~^~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> apply(std::vector<int>&, std::vector<int>&)':
potion.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(aid<a.size() || eid<ev.size()){
      |           ~~~^~~~~~~~~
potion.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(aid<a.size() || eid<ev.size()){
      |                           ~~~^~~~~~~~~~
potion.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if(eid>=ev.size()){
      |            ~~~^~~~~~~~~~~
potion.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         else if(aid>=a.size()){
      |                 ~~~^~~~~~~~~~
potion.cpp: In function 'int get_last(int, int)':
potion.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         if(cur+step<events[id].size()){
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~

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