oj.uz

Submission #872101

# Submission time Handle Problem Language Result Execution time Memory
872101 2023-11-12T10:07:43 Z Trisanu_Das The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2185 ms 96468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,set<pii>> piv;
 
int n,h[100005];
const int sq=50;
vector<pii> c[100005];
vector<piv> v[100005];
 
bool comp(int a, int b) {return h[a]<h[b];}
 
void init(int N, int D, int H[]) {
    n=N;
    for (int i=0; i<n; ++i) h[i]=H[i], v[i].push_back(piv(0,{}));
}
 
void curseChanges(int U, int A[], int B[]) {
    for (int i=0; i<U; ++i) {
        c[A[i]].push_back(pii(i+1,B[i]));
        c[B[i]].push_back(pii(i+1,A[i]));
    }
 
    for (int i=0; i<n; ++i) {
        set<pii> temp;
        for (int j=0; j<c[i].size(); ++j) {
            int add=c[i][j].second;
            if (temp.find(pii(h[add],add))==temp.end()) temp.insert(pii(h[add],add));
            else temp.erase(temp.find(pii(h[add],add)));
            if ((j+1)%sq==0) v[i].push_back(piv(c[i][j].first,temp));
        }
    }
}
 
int question(int x, int y, int day) {
    int hx=upper_bound(v[x].begin(),v[x].end(),piv(day+1,{}))-v[x].begin()-1;
    int hy=upper_bound(v[y].begin(),v[y].end(),piv(day+1,{}))-v[y].begin()-1;
 
    set<pii> tempX=v[x][hx].second, tempY=v[y][hy].second;
 
    int Hx=upper_bound(c[x].begin(),c[x].end(),pii(v[x][hx].first,INT_MAX))-c[x].begin();
    int Hy=upper_bound(c[y].begin(),c[y].end(),pii(v[y][hy].first,INT_MAX))-c[y].begin();
 
    while (Hx<c[x].size() && c[x][Hx].first<=day) {
        int add=c[x][Hx].second;
        if (tempX.find(pii(h[add],add))==tempX.end()) tempX.insert(pii(h[add],add));
        else tempX.erase(tempX.find(pii(h[add],add)));
        ++Hx;
    }
 
    while (Hy<c[y].size() && c[y][Hy].first<=day) {
        int add=c[y][Hy].second;
        if (tempY.find(pii(h[add],add))==tempY.end()) tempY.insert(pii(h[add],add));
        else tempY.erase(tempY.find(pii(h[add],add)));
        ++Hy;
    }
 
    int ans=1e9;
    auto itx=tempX.begin(), ity=tempY.begin();
    while (itx!=tempX.end() && ity!=tempY.end()) {
        ans=min(ans,abs((*itx).first-(*ity).first));
        if ((*itx).first<(*ity).first) ++itx;
        else ++ity;
    }
    return ans;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int j=0; j<c[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while (Hx<c[x].size() && c[x][Hx].first<=day) {
      |            ~~^~~~~~~~~~~~
potion.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (Hy<c[y].size() && c[y][Hy].first<=day) {
      |            ~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 18 ms 12372 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 20176 KB Output is correct
2 Correct 144 ms 20168 KB Output is correct
3 Correct 302 ms 21216 KB Output is correct
4 Correct 1351 ms 58244 KB Output is correct
5 Correct 481 ms 14036 KB Output is correct
6 Correct 2185 ms 86780 KB Output is correct
7 Correct 634 ms 26248 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 20288 KB Output is correct
2 Correct 1584 ms 93644 KB Output is correct
3 Correct 1062 ms 52868 KB Output is correct
4 Correct 1691 ms 85800 KB Output is correct
5 Correct 267 ms 23908 KB Output is correct
6 Correct 1868 ms 86464 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6232 KB Output is correct
2 Correct 161 ms 6488 KB Output is correct
3 Correct 259 ms 6232 KB Output is correct
4 Correct 798 ms 7824 KB Output is correct
5 Correct 704 ms 7000 KB Output is correct
6 Correct 133 ms 5592 KB Output is correct
7 Correct 701 ms 7512 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 18 ms 12372 KB Output is correct
6 Correct 145 ms 20176 KB Output is correct
7 Correct 144 ms 20168 KB Output is correct
8 Correct 302 ms 21216 KB Output is correct
9 Correct 1351 ms 58244 KB Output is correct
10 Correct 481 ms 14036 KB Output is correct
11 Correct 2185 ms 86780 KB Output is correct
12 Correct 634 ms 26248 KB Output is correct
13 Correct 156 ms 20288 KB Output is correct
14 Correct 1584 ms 93644 KB Output is correct
15 Correct 1062 ms 52868 KB Output is correct
16 Correct 1691 ms 85800 KB Output is correct
17 Correct 267 ms 23908 KB Output is correct
18 Correct 1868 ms 86464 KB Output is correct
19 Correct 32 ms 6232 KB Output is correct
20 Correct 161 ms 6488 KB Output is correct
21 Correct 259 ms 6232 KB Output is correct
22 Correct 798 ms 7824 KB Output is correct
23 Correct 704 ms 7000 KB Output is correct
24 Correct 133 ms 5592 KB Output is correct
25 Correct 701 ms 7512 KB Output is correct
26 Correct 748 ms 41668 KB Output is correct
27 Correct 1135 ms 52676 KB Output is correct
28 Correct 1147 ms 47884 KB Output is correct
29 Correct 1217 ms 58688 KB Output is correct
30 Correct 2161 ms 86244 KB Output is correct
31 Correct 1904 ms 96468 KB Output is correct
32 Correct 2000 ms 86656 KB Output is correct