oj.uz

Submission #798762

# Submission time Handle Problem Language Result Execution time Memory
798762 2023-07-31T03:42:35 Z PoonYaPat The Potion of Great Power (CEOI20_potion) C++14
17 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,vector<int>> piv;
typedef pair<int,int> pii;

int n,h[100005];
const int sq=300;
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) {
        vector<int> temp,temp2;
        v[i].push_back(piv(0,{}));

        for (int j=0; j<c[i].size(); ++j) {
            int add=c[i][j].second;
            bool have=false;
            for (auto s : temp) if (s==add) have=true;

            if (have) {
                for (auto s : temp) if (s!=add) temp2.push_back(s);
            } else {
                bool f=false;
                for (auto s : temp) {
                    if (h[s]<h[add]) temp2.push_back(s);
                    else {
                        if (!f) {
                            temp2.push_back(add);
                            temp2.push_back(s);
                        } else temp2.push_back(s);
                    }
                }
                if (!f) temp2.push_back(add);
            }
            swap(temp,temp2);
            temp2.clear();

            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;

    vector<int> tempx=v[x][hx].second,tempy=v[y][hy].second;
    map<int,int> haveX,haveY;
    for (auto s : tempx) haveX[s]++;
    for (auto s : tempy) haveY[s]++;

    int Hx=upper_bound(c[x].begin(),c[x].end(),pii(v[x][hx].first,INT_MAX))-c[x].begin();
    while (Hx<c[x].size() && c[x][Hx].first<=day) tempx.push_back(c[x][Hx].second), ++haveX[c[x][Hx].second], ++Hx;

    int Hy=upper_bound(c[y].begin(),c[y].end(),pii(v[y][hy].first,INT_MAX))-c[y].begin();
    while (Hy<c[y].size() && c[y][Hy].first<=day) tempy.push_back(c[y][Hy].second), ++haveY[c[y][Hy].second], ++Hy;

    sort(tempx.begin(),tempx.end(),comp);
    sort(tempy.begin(),tempy.end(),comp);

    int xi=0, yi=0, nx=tempx.size(), ny=tempy.size();

    int ans=1e9;
    while (xi<nx && yi<ny) {
        if (haveX[tempx[xi]]%2==0) ++xi;
        else if (haveY[tempy[yi]]%2==0) ++yi;
        else {
            ans=min(ans,abs(h[tempx[xi]]-h[tempy[yi]]));
            if (h[tempx[xi]]>h[tempy[yi]]) ++yi;
            else ++xi;
        }
    }
    return ans;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:27: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]
   27 |         for (int j=0; j<c[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:65: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]
   65 |     while (Hx<c[x].size() && c[x][Hx].first<=day) tempx.push_back(c[x][Hx].second), ++haveX[c[x][Hx].second], ++Hx;
      |            ~~^~~~~~~~~~~~
potion.cpp:68: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]
   68 |     while (Hy<c[y].size() && c[y][Hy].first<=day) tempy.push_back(c[y][Hy].second), ++haveY[c[y][Hy].second], ++Hy;
      |            ~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 24 ms 13612 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 21360 KB Output is correct
2 Correct 202 ms 21476 KB Output is correct
3 Incorrect 1970 ms 29532 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 21380 KB Output is correct
2 Runtime error 409 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6352 KB Output is correct
2 Correct 370 ms 6480 KB Output is correct
3 Execution timed out 3040 ms 214604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 5 ms 5200 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 24 ms 13612 KB Output is correct
6 Correct 199 ms 21360 KB Output is correct
7 Correct 202 ms 21476 KB Output is correct
8 Incorrect 1970 ms 29532 KB Incorrect
9 Halted 0 ms 0 KB -