oj.uz

Submission #793128

# Submission time Handle Problem Language Result Execution time Memory
793128 2023-07-25T14:13:38 Z JakobZorz The Potion of Great Power (CEOI20_potion) C++14
70 / 100
 3000 ms 216492 KB 
#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<30;
const int NUM_NODES=1e8;

vector<int>elements;

int val[NUM_NODES];
int ch1[NUM_NODES];
int ch2[NUM_NODES];
int curr_node=1;

void collect_fn(int node,int l,int r){
    if(l==r-1){
        if(val[node]!=0)
            elements.push_back(l);
        return;
    }
    int m=(l+r)/2;
    if(ch1[node]!=0)
        collect_fn(ch1[node],l,m);
    if(ch2[node]!=0)
        collect_fn(ch2[node],m,r);
}

vector<int>collect(int node){
    elements.clear();
    collect_fn(node,0,TREE_SIZE);
    return elements;
}

int insert_fn(int old_node,int x,int q,int l,int r){
    if(x<l||r<=x)
        return old_node;
    
    int node=curr_node++;
    if(old_node){
        ch1[node]=ch1[old_node];
        ch2[node]=ch2[old_node];
        val[node]=val[old_node];
    }
    
    if(l==r-1){
        val[node]+=q;
    }else{
        int m=(l+r)/2;
        ch1[node]=insert_fn(ch1[node],x,q,l,m);
        ch2[node]=insert_fn(ch2[node],x,q,m,r);
    }
    
    if(ch1[node]==0&&ch2[node]==0&&val[node]==0)
        return 0;
    
    return node;
}

int insert(int old_node,int x,int q){
    return insert_fn(old_node,x,q,0,TREE_SIZE);
}

// time travelling multiset
class TTMS{
    vector<int>days;
    vector<int>sets;
    vector<vector<int>>collected;
    vector<bool>collectedt;
public:
    TTMS(){
        days={-1};
        sets={curr_node++};
        collected={{}};
        collectedt={false};
    }
    
    void add_new_day(int day){
        days.push_back(day);
        sets.push_back(sets.back());
        collected.push_back({});
        collectedt.push_back(false);
    }
    
    void insert(int el){
        sets.back()=::insert(sets.back(),el,1);
    }
    
    void remove(int el){
        sets.back()=::insert(sets.back(),el,-1);
    }
    
    vector<int> get(int day){
        int l=0,r=(int)sets.size();
        while(l!=r-1){
            int m=(l+r)/2;
            if(day<days[m])
                r=m;
            else
                l=m;
        }
        if(collectedt[l])
            return collected[l];
        vector<int>res=collect(sets[l]);
        collectedt[l]=true;
        collected[l]=res;
        return res;
    }
};


int get_closest(vector<int>a,vector<int>b){
    int res=1e9;
    int i=0,j=0;
    while(i<(int)a.size()&&j<(int)b.size()){
        res=min(res,abs(a[i]-b[j]));
        if(i<(int)a.size()&&a[i]<=b[j])
            i++;
        else if(j<(int)b.size()&&b[j]<=a[i])
            j++;
    }
    return res;
}


int n;
int heights[100000];
TTMS ttms[100000];

void init(int N, int D, int H[]) {
    n=N;
    for(int i=0;i<n;i++)
        heights[i]=H[i];
}

ll to(int a,int b){
    if(a<b)
        swap(a,b);
    return a+((ll)b<<32);
}

void curseChanges(int U, int A[], int B[]) {
    unordered_set<ll>conns;
    for(int day=0;day<U;day++){
        int a=A[day],b=B[day];
        ll conn=to(a,b);
        ttms[a].add_new_day(day+1);
        ttms[b].add_new_day(day+1);
        if(conns.find(conn)==conns.end()){
            conns.insert(conn);
            ttms[a].insert(heights[b]);
            ttms[b].insert(heights[a]);
        }else{
            conns.erase(conn);
            ttms[a].remove(heights[b]);
            ttms[b].remove(heights[a]);
        }
    }
}


unordered_map<ll,int>dp;
int question(int x, int y, int v) {
    ll k=x+(ll)1e5*y+(ll)1e10*v;
    if(dp.find(k)!=dp.end())
        return dp[k];
    
    vector<int>a=ttms[x].get(v);
    vector<int>b=ttms[y].get(v);
    
    int res=get_closest(a,b);
    dp[k]=res;
    return res;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24692 KB Output is correct
2 Correct 29 ms 24708 KB Output is correct
3 Correct 24 ms 24672 KB Output is correct
4 Correct 33 ms 25428 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 197616 KB Output is correct
2 Correct 857 ms 197512 KB Output is correct
3 Correct 269 ms 187512 KB Output is correct
4 Correct 726 ms 193612 KB Output is correct
5 Correct 787 ms 200224 KB Output is correct
6 Correct 596 ms 190084 KB Output is correct
7 Correct 609 ms 192520 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 197524 KB Output is correct
2 Correct 379 ms 192284 KB Output is correct
3 Correct 506 ms 190728 KB Output is correct
4 Correct 501 ms 190652 KB Output is correct
5 Correct 650 ms 197236 KB Output is correct
6 Correct 493 ms 190784 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 34876 KB Output is correct
2 Correct 120 ms 35140 KB Output is correct
3 Correct 128 ms 34460 KB Output is correct
4 Correct 409 ms 39440 KB Output is correct
5 Correct 351 ms 38404 KB Output is correct
6 Correct 124 ms 35284 KB Output is correct
7 Correct 359 ms 39080 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 23 ms 24692 KB Output is correct
3 Correct 29 ms 24708 KB Output is correct
4 Correct 24 ms 24672 KB Output is correct
5 Correct 33 ms 25428 KB Output is correct
6 Correct 837 ms 197616 KB Output is correct
7 Correct 857 ms 197512 KB Output is correct
8 Correct 269 ms 187512 KB Output is correct
9 Correct 726 ms 193612 KB Output is correct
10 Correct 787 ms 200224 KB Output is correct
11 Correct 596 ms 190084 KB Output is correct
12 Correct 609 ms 192520 KB Output is correct
13 Correct 642 ms 197524 KB Output is correct
14 Correct 379 ms 192284 KB Output is correct
15 Correct 506 ms 190728 KB Output is correct
16 Correct 501 ms 190652 KB Output is correct
17 Correct 650 ms 197236 KB Output is correct
18 Correct 493 ms 190784 KB Output is correct
19 Correct 81 ms 34876 KB Output is correct
20 Correct 120 ms 35140 KB Output is correct
21 Correct 128 ms 34460 KB Output is correct
22 Correct 409 ms 39440 KB Output is correct
23 Correct 351 ms 38404 KB Output is correct
24 Correct 124 ms 35284 KB Output is correct
25 Correct 359 ms 39080 KB Output is correct
26 Execution timed out 3070 ms 216492 KB Time limit exceeded
27 Halted 0 ms 0 KB -