oj.uz

Submission #966845

# Submission time Handle Problem Language Result Execution time Memory
966845 2024-04-20T13:16:54 Z anton The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 203792 KB 
#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.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

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

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1620 KB Output is correct
2 Correct 3 ms 1544 KB Output is correct
3 Correct 3 ms 1368 KB Output is correct
4 Correct 35 ms 14324 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 203792 KB Output is correct
2 Correct 896 ms 203724 KB Output is correct
3 Correct 343 ms 90616 KB Output is correct
4 Correct 2413 ms 143560 KB Output is correct
5 Correct 1314 ms 185332 KB Output is correct
6 Execution timed out 3022 ms 132112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 203488 KB Output is correct
2 Execution timed out 3070 ms 106968 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 11452 KB Output is correct
2 Correct 119 ms 7764 KB Output is correct
3 Correct 158 ms 6712 KB Output is correct
4 Correct 820 ms 8628 KB Output is correct
5 Correct 689 ms 10296 KB Output is correct
6 Correct 154 ms 9788 KB Output is correct
7 Correct 602 ms 7696 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 3 ms 1544 KB Output is correct
4 Correct 3 ms 1368 KB Output is correct
5 Correct 35 ms 14324 KB Output is correct
6 Correct 918 ms 203792 KB Output is correct
7 Correct 896 ms 203724 KB Output is correct
8 Correct 343 ms 90616 KB Output is correct
9 Correct 2413 ms 143560 KB Output is correct
10 Correct 1314 ms 185332 KB Output is correct
11 Execution timed out 3022 ms 132112 KB Time limit exceeded
12 Halted 0 ms 0 KB -