oj.uz

답안 #796711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796711 2023-07-28T15:58:54 Z JakobZorz The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1130 ms 25468 KB 
#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 / 0.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2768 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 10 ms 3492 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 25436 KB Output is correct
2 Correct 249 ms 25416 KB Output is correct
3 Correct 234 ms 7980 KB Output is correct
4 Correct 330 ms 17416 KB Output is correct
5 Correct 253 ms 24960 KB Output is correct
6 Correct 715 ms 13684 KB Output is correct
7 Correct 256 ms 13384 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 25468 KB Output is correct
2 Correct 508 ms 8524 KB Output is correct
3 Correct 302 ms 13848 KB Output is correct
4 Correct 407 ms 13636 KB Output is correct
5 Correct 215 ms 24956 KB Output is correct
6 Correct 410 ms 13528 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 3792 KB Output is correct
2 Correct 35 ms 2972 KB Output is correct
3 Correct 122 ms 2924 KB Output is correct
4 Correct 183 ms 3428 KB Output is correct
5 Correct 145 ms 3704 KB Output is correct
6 Correct 32 ms 3792 KB Output is correct
7 Correct 436 ms 3096 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 3 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2768 KB Output is correct
5 Correct 10 ms 3492 KB Output is correct
6 Correct 220 ms 25436 KB Output is correct
7 Correct 249 ms 25416 KB Output is correct
8 Correct 234 ms 7980 KB Output is correct
9 Correct 330 ms 17416 KB Output is correct
10 Correct 253 ms 24960 KB Output is correct
11 Correct 715 ms 13684 KB Output is correct
12 Correct 256 ms 13384 KB Output is correct
13 Correct 243 ms 25468 KB Output is correct
14 Correct 508 ms 8524 KB Output is correct
15 Correct 302 ms 13848 KB Output is correct
16 Correct 407 ms 13636 KB Output is correct
17 Correct 215 ms 24956 KB Output is correct
18 Correct 410 ms 13528 KB Output is correct
19 Correct 25 ms 3792 KB Output is correct
20 Correct 35 ms 2972 KB Output is correct
21 Correct 122 ms 2924 KB Output is correct
22 Correct 183 ms 3428 KB Output is correct
23 Correct 145 ms 3704 KB Output is correct
24 Correct 32 ms 3792 KB Output is correct
25 Correct 436 ms 3096 KB Output is correct
26 Correct 313 ms 8604 KB Output is correct
27 Correct 429 ms 13900 KB Output is correct
28 Correct 405 ms 20456 KB Output is correct
29 Correct 332 ms 17308 KB Output is correct
30 Correct 729 ms 13708 KB Output is correct
31 Correct 1130 ms 8420 KB Output is correct
32 Correct 679 ms 13576 KB Output is correct