Submission #946127

#TimeUsernameProblemLanguageResultExecution timeMemory
946127berrThe Potion of Great Power (CEOI20_potion)C++17
100 / 100
2694 ms28940 KiB
#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%500) 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 (stderr)

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()){
      |                 ~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...