Submission #946126

#	Time	Username	Problem	Language	Result	Execution time	Memory
946126		berr	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	875 ms	30572 KiB

potion

//#define _GLIBCXX_DEBUG

#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, 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,pe=5000;
    while(pe--){
        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 (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:34: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]
   34 |         for(int j=0; j<op[i].size(); j++){
      |                      ~^~~~~~~~~~~~~
potion.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 for(int l=1; l<st.size(); l++){
      |                              ~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:78: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]
   78 |     for(int i=a[x][posx][1]+1; i<op[x].size()&&op[x][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:82: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]
   82 |     for(int i=a[y][posy][1]+1; i<op[y].size()&&op[y][i][0]<=v; i++){
      |                                ~^~~~~~~~~~~~~
potion.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int l=1; l<xx.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int l=1; l<yy.size(); l++){
      |                  ~^~~~~~~~~~
potion.cpp:132:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         if(itrx>=xr.size() && itx>=b[x][posx].size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:132:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         if(itrx>=xr.size() && itx>=b[x][posx].size()) break;
      |                               ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:133:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         if(itry>=yr.size() && ity>=b[y][posy].size()) break;
      |            ~~~~^~~~~~~~~~~
potion.cpp:133:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         if(itry>=yr.size() && ity>=b[y][posy].size()) break;
      |                               ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         if(itrx < xr.size() && itx < b[x][posx].size()){
      |            ~~~~~^~~~~~~~~~~
potion.cpp:138:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         if(itrx < xr.size() && itx < b[x][posx].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         else if(itrx<xr.size()){
      |                 ~~~~^~~~~~~~~~
potion.cpp:156:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         if(itry < yr.size() && ity < b[y][posy].size()){
      |            ~~~~~^~~~~~~~~~~
potion.cpp:156:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         if(itry < yr.size() && ity < b[y][posy].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:168:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         else if(itry<yr.size()){
      |                 ~~~~^~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30