oj.uz

답안 #794601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794601 2023-07-26T16:15:45 Z JakobZorz The Potion of Great Power (CEOI20_potion) C++14
52 / 100
 3000 ms 89632 KB 
#include<iostream>
#include<set>
#include<vector>
#include<unordered_set>
using namespace std;
typedef long long ll;

int u;

const int C=64;

// time travelling multiset
class TTMS{
    vector<int>days;
    vector<pair<int,int>>changes;
    vector<multiset<int>>checkpoints;
    multiset<int>curr_set;
    int curr_day=0;
    void add_day(){
        days.push_back(curr_day);
        if(checkpoints.size()*C<days.size())
            checkpoints.push_back(curr_set);
    }
public:
    TTMS(){
        checkpoints={};
    }
    
    void add_new_day(int day){
        curr_day=day;
    }
    
    void insert(int el){
        add_day();
        curr_set.insert(el);
        changes.push_back({el,1});
    }
    
    void remove(int el){
        add_day();
        curr_set.erase(curr_set.find(el));
        changes.push_back({el,-1});
    }
    
    vector<int> get(int day){
        if(day==u)
            return{curr_set.begin(),curr_set.end()};
        
        multiset<int>s;
        
        int l=0,r=(int)days.size();
        while(l<r-1){
            int m=(l+r)/2;
            if(days[m]<=day)
                l=m;
            else
                r=m;
        }
        
        int idx=l;
        if(idx/C>=(int)checkpoints.size())
            s=curr_set;
        else
            s=checkpoints[idx/C];
        
        for(int i=idx/C*C;i<(int)changes.size();i++){
            if(days[i]>day)
                break;
            if(changes[i].second==1)
                s.insert(changes[i].first);
            else if(changes[i].second==-1)
                s.erase(s.find(changes[i].first));
        }
        return{s.begin(),s.end()};
    }
};

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[]) {
    u=U;
    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]);
        }
    }
}

int question(int x, int y, int v) {
    vector<int>a=ttms[x].get(v);
    vector<int>b=ttms[y].get(v);
    
    return get_closest(a,b);
}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12752 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12988 KB Output is correct
2 Correct 8 ms 13008 KB Output is correct
3 Correct 7 ms 13008 KB Output is correct
4 Correct 16 ms 13944 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 387 ms 58380 KB Output is correct
2 Correct 398 ms 58416 KB Output is correct
3 Correct 120 ms 23324 KB Output is correct
4 Correct 1461 ms 71604 KB Output is correct
5 Correct 699 ms 50164 KB Output is correct
6 Correct 2357 ms 89632 KB Output is correct
7 Correct 464 ms 42992 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 58348 KB Output is correct
2 Correct 1863 ms 83808 KB Output is correct
3 Correct 1504 ms 63324 KB Output is correct
4 Execution timed out 3042 ms 89288 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 15412 KB Output is correct
2 Correct 150 ms 13536 KB Output is correct
3 Correct 249 ms 13448 KB Output is correct
4 Correct 779 ms 15632 KB Output is correct
5 Correct 1104 ms 15940 KB Output is correct
6 Correct 130 ms 14544 KB Output is correct
7 Correct 707 ms 14556 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12752 KB Output is correct
2 Correct 8 ms 12988 KB Output is correct
3 Correct 8 ms 13008 KB Output is correct
4 Correct 7 ms 13008 KB Output is correct
5 Correct 16 ms 13944 KB Output is correct
6 Correct 387 ms 58380 KB Output is correct
7 Correct 398 ms 58416 KB Output is correct
8 Correct 120 ms 23324 KB Output is correct
9 Correct 1461 ms 71604 KB Output is correct
10 Correct 699 ms 50164 KB Output is correct
11 Correct 2357 ms 89632 KB Output is correct
12 Correct 464 ms 42992 KB Output is correct
13 Correct 358 ms 58348 KB Output is correct
14 Correct 1863 ms 83808 KB Output is correct
15 Correct 1504 ms 63324 KB Output is correct
16 Execution timed out 3042 ms 89288 KB Time limit exceeded
17 Halted 0 ms 0 KB -