oj.uz

Submission #946132

# Submission time Handle Problem Language Result Execution time Memory
946132 2024-03-14T10:44:03 Z berr The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1906 ms 30364 KB 
#include <bits/stdc++.h>
using namespace std;
 
int n, d;
vector<int> h;
vector<vector<array<int, 2>>> a;
vector<vector<array<int, 2>>> op;
vector<vector<vector<int>>> b;
 
void init(int N, int D, int H[]){
 
    n = N; d = D;
    a.resize(n);
    b.resize(n);
    op.resize(n);
    for(int i=0; i<n; i++) h.push_back(H[i]);
    vector<int> emp;
    for(int i=0; i<n; i++){
        a[i].push_back({0, 0});
        b[i].push_back(emp);
    }
}
 
void curseChanges(int U, int A[], int B[]){
    for(int i=1; i<=U; i++){
        op[B[i-1]].push_back({i, A[i-1]});
        op[A[i-1]].push_back({i, B[i-1]});
    }
 
    for(int i=0; i<n; i++){
        vector<int> st;
        for(int j=0; j<op[i].size(); j++){
            st.push_back(op[i][j][1]);
            if(j%100) continue;
 
                vector<int>ar;
               
                sort(st.begin(), st.end(), [&](int x, int y){
                    if(h[x]!=h[y]) return h[x]<h[y];
                    return x<y;
                });
                int k=1;
                for(int l=1; l<st.size(); l++){
                    if(st[l]==st[l-1]) k++;
                    else{
                        if(k%2==1){
                            ar.push_back(st[l-1]);
                        }
                        k=1;
                    }
                }
 
                if(k%2==1){
                    ar.push_back(st.back());
                }
 
                a[i].push_back({op[i][j][0], j});
                b[i].push_back(ar);
                st = ar;
 
            }            
            
        
    }
}
 
 
int question(int x, int y, int v){
 
    int posx=lower_bound(a[x].begin(), a[x].end(), (array<int, 2>){v+1, 0})-a[x].begin()-1;
    int posy=lower_bound(a[y].begin(), a[y].end(),(array<int, 2>){v+1, 0})-a[y].begin()-1;
 
 
    vector<int> xx=b[x][posx], yy=b[y][posy], xr, yr;
 
    for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
        xx.push_back(op[x][i][1]);
    }
 
    for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
        yy.push_back(op[y][i][1]);
    }
    sort(xx.begin(), xx.end(), [&](int x, int y){
 
        if(h[x]!=h[y]) return h[x]<h[y];
        return x<y;
    });
 
    sort(yy.begin(), yy.end(), [&](int x, int y){
        if(h[x]!=h[y]) return h[x]<h[y];
        return x<y;
    });
 
 
    int k=1;
    for(int l=1; l<xx.size(); l++){
        if(xx[l]==xx[l-1]) k++;
        else{
            if(k%2==1){
                xr.push_back(xx[l-1]);
            }
            k=1;
        }
    }
 
    if(k%2==1&&xx.size()){
        xr.push_back(xx.back());
    }
    k=1;
    for(int l=1; l<yy.size(); l++){
        if(yy[l]==yy[l-1]) k++;
        else{
            if(k%2==1){
                yr.push_back(yy[l-1]);
            }
            k=1;
        }
    }
 
    if(k%2==1&&yy.size()){
        yr.push_back(yy.back());
    }
 
 
    int itrx=0, itry=0;
 
    int ans = 1e9;
    while(1){
        if(itrx>=xr.size()) break;
        if(itry>=yr.size()) break;
       
        ans=min(ans, abs(h[xr[itrx]]-h[yr[itry]]));
        if(h[xr[itrx]] < h[yr[itry]]) itrx++;
        else itry++;
 
    }
    return ans;
    return 1;
}/*
int main() {
  int N, D, U, Q;
  std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  std::cin >> N >> D >> U >> Q;
 
  int *F = new int[N];
  for (int i=0; i<N; i++)
    std::cin >> F[i];
  init(N, D, F);
 
  int *A = new int[U], *B = new int[U];
  for (int i=0; i<U; i++) {
    std::cin >> A[i] >> B[i];
  }
  curseChanges(U, A, B);
 
  bool correct = true;
  for (int i=0; i<Q; i++) {
    int X,Y,V,CorrectAnswer;
    std::cin >> X >> Y >> V >> CorrectAnswer;
    int YourAnswer = question(X,Y,V);
    if (YourAnswer != CorrectAnswer) {
      std::cout << "WA! Question: " << i
        << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
        <<  "Your answer: " << YourAnswer
                << " Correct Answer: " << CorrectAnswer << std::endl;
      correct = false;
    } else {
      //std::cerr << YourAnswer << " - OK" << std::endl;
    }
  }
  cout<<(float)(clock())/1000.0<<"\n";
 
  if (correct) {
    std::cout << "Correct." << std::endl;
  } else std::cout << "Incorrect." << std::endl;
    return 0;
 
}*/

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=0; j<op[i].size(); j++){
      |                      ~^~~~~~~~~~~~~
potion.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 for(int l=1; l<st.size(); l++){
      |                              ~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:76:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:80:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int l=1; l<xx.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int l=1; l<yy.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         if(itrx>=xr.size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         if(itry>=yr.size()) break;
      |            ~~~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 24 ms 14968 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 28284 KB Output is correct
2 Correct 174 ms 28440 KB Output is correct
3 Correct 327 ms 20300 KB Output is correct
4 Correct 1072 ms 8744 KB Output is correct
5 Correct 281 ms 9172 KB Output is correct
6 Correct 1906 ms 29764 KB Output is correct
7 Correct 617 ms 27888 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 28592 KB Output is correct
2 Correct 1446 ms 26748 KB Output is correct
3 Correct 895 ms 28424 KB Output is correct
4 Correct 1610 ms 29880 KB Output is correct
5 Correct 255 ms 28656 KB Output is correct
6 Correct 1731 ms 30168 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2860 KB Output is correct
2 Correct 139 ms 2216 KB Output is correct
3 Correct 275 ms 2496 KB Output is correct
4 Correct 660 ms 2772 KB Output is correct
5 Correct 641 ms 2864 KB Output is correct
6 Correct 94 ms 856 KB Output is correct
7 Correct 619 ms 2344 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 24 ms 14968 KB Output is correct
6 Correct 216 ms 28284 KB Output is correct
7 Correct 174 ms 28440 KB Output is correct
8 Correct 327 ms 20300 KB Output is correct
9 Correct 1072 ms 8744 KB Output is correct
10 Correct 281 ms 9172 KB Output is correct
11 Correct 1906 ms 29764 KB Output is correct
12 Correct 617 ms 27888 KB Output is correct
13 Correct 176 ms 28592 KB Output is correct
14 Correct 1446 ms 26748 KB Output is correct
15 Correct 895 ms 28424 KB Output is correct
16 Correct 1610 ms 29880 KB Output is correct
17 Correct 255 ms 28656 KB Output is correct
18 Correct 1731 ms 30168 KB Output is correct
19 Correct 38 ms 2860 KB Output is correct
20 Correct 139 ms 2216 KB Output is correct
21 Correct 275 ms 2496 KB Output is correct
22 Correct 660 ms 2772 KB Output is correct
23 Correct 641 ms 2864 KB Output is correct
24 Correct 94 ms 856 KB Output is correct
25 Correct 619 ms 2344 KB Output is correct
26 Correct 659 ms 25252 KB Output is correct
27 Correct 920 ms 28640 KB Output is correct
28 Correct 1004 ms 29216 KB Output is correct
29 Correct 912 ms 8544 KB Output is correct
30 Correct 1900 ms 30292 KB Output is correct
31 Correct 1646 ms 26652 KB Output is correct
32 Correct 1586 ms 30364 KB Output is correct