oj.uz

Submission #793132

# Submission time Handle Problem Language Result Execution time Memory
793132 2023-07-25T14:16:03 Z JakobZorz The Potion of Great Power (CEOI20_potion) C++14
70 / 100
 3000 ms 214840 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 20 ms 23808 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24660 KB Output is correct
2 Correct 24 ms 24672 KB Output is correct
3 Correct 26 ms 24680 KB Output is correct
4 Correct 41 ms 25364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 197528 KB Output is correct
2 Correct 859 ms 197520 KB Output is correct
3 Correct 285 ms 187420 KB Output is correct
4 Correct 657 ms 193636 KB Output is correct
5 Correct 776 ms 200152 KB Output is correct
6 Correct 737 ms 190060 KB Output is correct
7 Correct 629 ms 191604 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 197500 KB Output is correct
2 Correct 395 ms 190048 KB Output is correct
3 Correct 500 ms 190056 KB Output is correct
4 Correct 601 ms 189920 KB Output is correct
5 Correct 615 ms 197060 KB Output is correct
6 Correct 484 ms 189988 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 32560 KB Output is correct
2 Correct 143 ms 32844 KB Output is correct
3 Correct 130 ms 32996 KB Output is correct
4 Correct 410 ms 37160 KB Output is correct
5 Correct 363 ms 36128 KB Output is correct
6 Correct 153 ms 33008 KB Output is correct
7 Correct 351 ms 36676 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 35 ms 24660 KB Output is correct
3 Correct 24 ms 24672 KB Output is correct
4 Correct 26 ms 24680 KB Output is correct
5 Correct 41 ms 25364 KB Output is correct
6 Correct 908 ms 197528 KB Output is correct
7 Correct 859 ms 197520 KB Output is correct
8 Correct 285 ms 187420 KB Output is correct
9 Correct 657 ms 193636 KB Output is correct
10 Correct 776 ms 200152 KB Output is correct
11 Correct 737 ms 190060 KB Output is correct
12 Correct 629 ms 191604 KB Output is correct
13 Correct 644 ms 197500 KB Output is correct
14 Correct 395 ms 190048 KB Output is correct
15 Correct 500 ms 190056 KB Output is correct
16 Correct 601 ms 189920 KB Output is correct
17 Correct 615 ms 197060 KB Output is correct
18 Correct 484 ms 189988 KB Output is correct
19 Correct 90 ms 32560 KB Output is correct
20 Correct 143 ms 32844 KB Output is correct
21 Correct 130 ms 32996 KB Output is correct
22 Correct 410 ms 37160 KB Output is correct
23 Correct 363 ms 36128 KB Output is correct
24 Correct 153 ms 33008 KB Output is correct
25 Correct 351 ms 36676 KB Output is correct
26 Execution timed out 3029 ms 214840 KB Time limit exceeded
27 Halted 0 ms 0 KB -