Submission #796711

#	Time	Username	Problem	Language	Result	Execution time	Memory
796711		JakobZorz	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	1130 ms	25468 KiB

potion

#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;

struct Interval{
    int h,l,r;
};

bool cmp(Interval&a,Interval&b){
    return a.h<b.h;
}

int u,n;
int heights[100000];
vector<Interval>intervals[100000];

int get_closest(vector<Interval>&a,vector<Interval>&b,int day){
    int res=1e9;
    auto i=a.begin();
    auto j=b.begin();
    while(i!=a.end()&&j!=b.end()){
        while(i!=a.end()&&(day<=i->l||i->r<day))
            i++;
        while(j!=b.end()&&(day<=j->l||j->r<day))
            j++;
        if(i==a.end()||j==b.end())
            break;
        
        res=min(res,abs(i->h-j->h));
        if(i!=a.end()&&i->h<=j->h)
            i++;
        else if(j!=b.end()&&j->h<=i->h)
            j++;
    }
    return res;
}

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

void curseChanges(int U, int A[], int B[]){
    u=U;
    map<pair<int,int>,int>conns;
    for(int day=0;day<U;day++){
        int a=A[day],b=B[day];
        if(a>b)
            swap(a,b);
        
        if(conns.find({a,b})==conns.end()){
            conns[{a,b}]=day;
        }else{
            Interval interval;
            interval.l=conns[{a,b}];
            interval.r=day;
            
            interval.h=heights[a];
            intervals[b].push_back(interval);
            
            interval.h=heights[b];
            intervals[a].push_back(interval);
            
            conns.erase({a,b});
        }
    }
    
    for(auto i:conns){
        int a=i.first.first;
        int b=i.first.second;
        
        Interval interval;
        interval.l=i.second;
        interval.r=u;
        
        interval.h=heights[a];
        intervals[b].push_back(interval);
        
        interval.h=heights[b];
        intervals[a].push_back(interval);
    }
    
    for(int i=0;i<n;i++)
        sort(intervals[i].begin(),intervals[i].end(),cmp);
}

int question(int x, int y, int v) {
    return get_closest(intervals[x],intervals[y],v);
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30