oj.uz

Submission #946131

# Submission time Handle Problem Language Result Execution time Memory
946131 2024-03-14T10:43:08 Z berr The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1752 ms 33196 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%50) 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 1 ms 600 KB Output is correct
4 Correct 22 ms 15196 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 28500 KB Output is correct
2 Correct 173 ms 28684 KB Output is correct
3 Correct 221 ms 20452 KB Output is correct
4 Correct 890 ms 10796 KB Output is correct
5 Correct 241 ms 9168 KB Output is correct
6 Correct 1752 ms 33056 KB Output is correct
7 Correct 416 ms 28588 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 28332 KB Output is correct
2 Correct 1437 ms 30176 KB Output is correct
3 Correct 764 ms 29956 KB Output is correct
4 Correct 1406 ms 32900 KB Output is correct
5 Correct 256 ms 29340 KB Output is correct
6 Correct 1590 ms 33196 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2904 KB Output is correct
2 Correct 105 ms 2488 KB Output is correct
3 Correct 174 ms 2488 KB Output is correct
4 Correct 524 ms 3072 KB Output is correct
5 Correct 516 ms 3148 KB Output is correct
6 Correct 88 ms 1112 KB Output is correct
7 Correct 481 ms 2648 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 1 ms 600 KB Output is correct
5 Correct 22 ms 15196 KB Output is correct
6 Correct 184 ms 28500 KB Output is correct
7 Correct 173 ms 28684 KB Output is correct
8 Correct 221 ms 20452 KB Output is correct
9 Correct 890 ms 10796 KB Output is correct
10 Correct 241 ms 9168 KB Output is correct
11 Correct 1752 ms 33056 KB Output is correct
12 Correct 416 ms 28588 KB Output is correct
13 Correct 162 ms 28332 KB Output is correct
14 Correct 1437 ms 30176 KB Output is correct
15 Correct 764 ms 29956 KB Output is correct
16 Correct 1406 ms 32900 KB Output is correct
17 Correct 256 ms 29340 KB Output is correct
18 Correct 1590 ms 33196 KB Output is correct
19 Correct 44 ms 2904 KB Output is correct
20 Correct 105 ms 2488 KB Output is correct
21 Correct 174 ms 2488 KB Output is correct
22 Correct 524 ms 3072 KB Output is correct
23 Correct 516 ms 3148 KB Output is correct
24 Correct 88 ms 1112 KB Output is correct
25 Correct 481 ms 2648 KB Output is correct
26 Correct 524 ms 26192 KB Output is correct
27 Correct 805 ms 30172 KB Output is correct
28 Correct 912 ms 31124 KB Output is correct
29 Correct 745 ms 10816 KB Output is correct
30 Correct 1666 ms 33156 KB Output is correct
31 Correct 1536 ms 30500 KB Output is correct
32 Correct 1481 ms 33192 KB Output is correct