oj.uz

Submission #793117

# Submission time Handle Problem Language Result Execution time Memory
793117 2023-07-25T14:05:41 Z JakobZorz The Potion of Great Power (CEOI20_potion) C++14
70 / 100
 3000 ms 212332 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;
    for(int i:a)
        for(int j:b){
            res=min(res,abs(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 23760 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24708 KB Output is correct
2 Correct 23 ms 24644 KB Output is correct
3 Correct 24 ms 24732 KB Output is correct
4 Correct 32 ms 25384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 197472 KB Output is correct
2 Correct 828 ms 197516 KB Output is correct
3 Correct 360 ms 187416 KB Output is correct
4 Correct 2465 ms 193596 KB Output is correct
5 Correct 874 ms 200232 KB Output is correct
6 Correct 2728 ms 190028 KB Output is correct
7 Correct 700 ms 192448 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 197520 KB Output is correct
2 Correct 381 ms 192300 KB Output is correct
3 Correct 519 ms 190876 KB Output is correct
4 Correct 518 ms 190584 KB Output is correct
5 Correct 679 ms 197032 KB Output is correct
6 Correct 512 ms 190688 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 34912 KB Output is correct
2 Correct 117 ms 35180 KB Output is correct
3 Correct 120 ms 34468 KB Output is correct
4 Correct 1234 ms 39464 KB Output is correct
5 Correct 1273 ms 38420 KB Output is correct
6 Correct 134 ms 35348 KB Output is correct
7 Correct 761 ms 39000 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23760 KB Output is correct
2 Correct 23 ms 24708 KB Output is correct
3 Correct 23 ms 24644 KB Output is correct
4 Correct 24 ms 24732 KB Output is correct
5 Correct 32 ms 25384 KB Output is correct
6 Correct 839 ms 197472 KB Output is correct
7 Correct 828 ms 197516 KB Output is correct
8 Correct 360 ms 187416 KB Output is correct
9 Correct 2465 ms 193596 KB Output is correct
10 Correct 874 ms 200232 KB Output is correct
11 Correct 2728 ms 190028 KB Output is correct
12 Correct 700 ms 192448 KB Output is correct
13 Correct 674 ms 197520 KB Output is correct
14 Correct 381 ms 192300 KB Output is correct
15 Correct 519 ms 190876 KB Output is correct
16 Correct 518 ms 190584 KB Output is correct
17 Correct 679 ms 197032 KB Output is correct
18 Correct 512 ms 190688 KB Output is correct
19 Correct 95 ms 34912 KB Output is correct
20 Correct 117 ms 35180 KB Output is correct
21 Correct 120 ms 34468 KB Output is correct
22 Correct 1234 ms 39464 KB Output is correct
23 Correct 1273 ms 38420 KB Output is correct
24 Correct 134 ms 35348 KB Output is correct
25 Correct 761 ms 39000 KB Output is correct
26 Execution timed out 3045 ms 212332 KB Time limit exceeded
27 Halted 0 ms 0 KB -