oj.uz

Submission #946130

# Submission time Handle Problem Language Result Execution time Memory
946130 2024-03-14T10:40:24 Z berr The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 782 ms 33392 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, yy, 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 itx=0, ity=0;
    int itrx=0, itry=0;
 
    int ans = 1e9;
    while(1){
        if(itrx>=xr.size() && itx>=b[x][posx].size()) break;
        if(itry>=yr.size() && ity>=b[y][posy].size()) break;
        
        int valfirst, valsecond;
        int p1, p2;
        int check =0;
        if(itrx < xr.size() && itx < b[x][posx].size()){
            if(xr[itrx] == b[x][posx][itx]){
                itrx++; itx++;
                check=1;
            }
            else{
                valfirst=min(h[xr[itrx]],  h[b[x][posx][itx]]);
 
                if(h[xr[itrx]]<h[b[x][posx][itx]]) p1=0;
                else p1=1;
            }
        }
        else if(itrx<xr.size()){
            p1=0;
            valfirst=h[xr[itrx]];
        }
        else p1=1, valfirst=h[b[x][posx][itx]];
 
        if(itry < yr.size() && ity < b[y][posy].size()){
            if(yr[itry] == b[y][posy][ity]){
                itry++; ity++;
                check=1;
            }
            else{
                valsecond=min(h[yr[itry]],  h[b[y][posy][ity]]);
 
                if(h[yr[itry]]<h[b[y][posy][ity]]) p2=0;
                else p2=1;
            }
        }
        else if(itry<yr.size()){
            p2=0;
            valsecond=h[yr[itry]];
        }
        else p2=1, valsecond=h[b[y][posy][ity]];
        if(check) continue;
        ans=min(ans, abs(valfirst-valsecond));
 
        if(p1==0&&p2==0){
            if(h[xr[itrx]] < h[yr[itry]]) itrx++;
            else itry++;
        }
        else if(p1==0&&p2==1){
            if(h[xr[itrx]] < h[b[y][posy][ity]]) itrx++;
            else ity++;        
        }
        else if(p1==1&&p2==0){
            if(h[b[x][posx][itx]] < h[yr[itry]]) itx++;
            else itry++;  
        }
        else{
            if(h[b[x][posx][itx]] < h[b[y][posy][ity]]) itx++;
            else ity++;  
        }
 
    }
    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: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(itrx>=xr.size() && itx>=b[x][posx].size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:130:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         if(itrx>=xr.size() && itx>=b[x][posx].size()) break;
      |                               ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(itry>=yr.size() && ity>=b[y][posy].size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:131:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(itry>=yr.size() && ity>=b[y][posy].size()) break;
      |                               ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         if(itrx < xr.size() && itx < b[x][posx].size()){
      |            ~~~~~^~~~~~~~~~~
potion.cpp:136:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         if(itrx < xr.size() && itx < b[x][posx].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:148:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         else if(itrx<xr.size()){
      |                 ~~~~^~~~~~~~~~
potion.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         if(itry < yr.size() && ity < b[y][posy].size()){
      |            ~~~~~^~~~~~~~~~~
potion.cpp:154:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         if(itry < yr.size() && ity < b[y][posy].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:166:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         else if(itry<yr.size()){
      |                 ~~~~^~~~~~~~~~

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 1 ms 668 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 25 ms 14740 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 28516 KB Output is correct
2 Correct 182 ms 28736 KB Output is correct
3 Correct 210 ms 20200 KB Output is correct
4 Correct 479 ms 10780 KB Output is correct
5 Correct 263 ms 9532 KB Output is correct
6 Correct 782 ms 33392 KB Output is correct
7 Correct 357 ms 28960 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 28516 KB Output is correct
2 Correct 443 ms 29968 KB Output is correct
3 Correct 357 ms 29884 KB Output is correct
4 Correct 472 ms 32744 KB Output is correct
5 Correct 194 ms 29000 KB Output is correct
6 Correct 491 ms 32896 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3088 KB Output is correct
2 Correct 108 ms 2648 KB Output is correct
3 Correct 152 ms 2392 KB Output is correct
4 Correct 280 ms 2904 KB Output is correct
5 Correct 231 ms 3036 KB Output is correct
6 Correct 92 ms 856 KB Output is correct
7 Correct 245 ms 2392 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 1 ms 668 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 25 ms 14740 KB Output is correct
6 Correct 191 ms 28516 KB Output is correct
7 Correct 182 ms 28736 KB Output is correct
8 Correct 210 ms 20200 KB Output is correct
9 Correct 479 ms 10780 KB Output is correct
10 Correct 263 ms 9532 KB Output is correct
11 Correct 782 ms 33392 KB Output is correct
12 Correct 357 ms 28960 KB Output is correct
13 Correct 160 ms 28516 KB Output is correct
14 Correct 443 ms 29968 KB Output is correct
15 Correct 357 ms 29884 KB Output is correct
16 Correct 472 ms 32744 KB Output is correct
17 Correct 194 ms 29000 KB Output is correct
18 Correct 491 ms 32896 KB Output is correct
19 Correct 34 ms 3088 KB Output is correct
20 Correct 108 ms 2648 KB Output is correct
21 Correct 152 ms 2392 KB Output is correct
22 Correct 280 ms 2904 KB Output is correct
23 Correct 231 ms 3036 KB Output is correct
24 Correct 92 ms 856 KB Output is correct
25 Correct 245 ms 2392 KB Output is correct
26 Correct 349 ms 25784 KB Output is correct
27 Correct 455 ms 29912 KB Output is correct
28 Correct 431 ms 30380 KB Output is correct
29 Correct 422 ms 10988 KB Output is correct
30 Correct 720 ms 32908 KB Output is correct
31 Correct 664 ms 30344 KB Output is correct
32 Correct 723 ms 32672 KB Output is correct