oj.uz

Submission #966881

# Submission time Handle Problem Language Result Execution time Memory
966881 2024-04-20T14:14:44 Z anton The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 945 ms 203376 KB 
#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 = 2;

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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 35 ms 14252 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 55784 KB Output is correct
2 Correct 502 ms 55948 KB Output is correct
3 Correct 243 ms 41764 KB Output is correct
4 Correct 664 ms 127212 KB Output is correct
5 Correct 471 ms 55804 KB Output is correct
6 Correct 905 ms 184232 KB Output is correct
7 Correct 460 ms 58996 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 56160 KB Output is correct
2 Correct 653 ms 197072 KB Output is correct
3 Correct 600 ms 113052 KB Output is correct
4 Correct 787 ms 183368 KB Output is correct
5 Correct 537 ms 64044 KB Output is correct
6 Correct 792 ms 184032 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4204 KB Output is correct
2 Correct 65 ms 3568 KB Output is correct
3 Correct 65 ms 3416 KB Output is correct
4 Correct 154 ms 6036 KB Output is correct
5 Correct 148 ms 5720 KB Output is correct
6 Correct 66 ms 2648 KB Output is correct
7 Correct 135 ms 5404 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 35 ms 14252 KB Output is correct
6 Correct 538 ms 55784 KB Output is correct
7 Correct 502 ms 55948 KB Output is correct
8 Correct 243 ms 41764 KB Output is correct
9 Correct 664 ms 127212 KB Output is correct
10 Correct 471 ms 55804 KB Output is correct
11 Correct 905 ms 184232 KB Output is correct
12 Correct 460 ms 58996 KB Output is correct
13 Correct 535 ms 56160 KB Output is correct
14 Correct 653 ms 197072 KB Output is correct
15 Correct 600 ms 113052 KB Output is correct
16 Correct 787 ms 183368 KB Output is correct
17 Correct 537 ms 64044 KB Output is correct
18 Correct 792 ms 184032 KB Output is correct
19 Correct 45 ms 4204 KB Output is correct
20 Correct 65 ms 3568 KB Output is correct
21 Correct 65 ms 3416 KB Output is correct
22 Correct 154 ms 6036 KB Output is correct
23 Correct 148 ms 5720 KB Output is correct
24 Correct 66 ms 2648 KB Output is correct
25 Correct 135 ms 5404 KB Output is correct
26 Correct 446 ms 88408 KB Output is correct
27 Correct 658 ms 112884 KB Output is correct
28 Correct 716 ms 108336 KB Output is correct
29 Correct 674 ms 127916 KB Output is correct
30 Correct 945 ms 183616 KB Output is correct
31 Correct 758 ms 203376 KB Output is correct
32 Correct 873 ms 184144 KB Output is correct