제출 #466636

#제출 시각아이디문제언어결과실행 시간메모리
466636ivan_tudorThe Potion of Great Power (CEOI20_potion)C++14
17 / 100
3075 ms19228 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int BUCKET_SIZE = 50; int h[N]; int n, d; int lg2[2*N]; void init(int N, int D, int H[]) { d = D; n = N; for(int i = 0; i < N; i++){ h[i] = H[i]; } } struct otherhelper{ int x; int time; }; vector <otherhelper> changes[N]; struct sethelper{ vector<int> act; int time; int pos; }; vector<vector<int>> precalc[N]; bool mark[N]; set<int> act; void curseChanges(int U, int A[], int B[]) { lg2[1] = 0; for(int i = 2; i < N; i++) lg2[i] = 1 + lg2[i/2]; for(int i = 0; i < U; i++){ changes[A[i]].push_back({B[i], i}); changes[B[i]].push_back({A[i], i}); } for(int i = 0; i < n; i++){ int cnt = 0; for(int j = 0; j < changes[i].size(); j++){ int val = changes[i][j].x; mark[val]^= true; if(mark[val] == false) act.erase(val); else act.insert(val); cnt++; if(cnt == BUCKET_SIZE){ precalc[i].push_back(vector<int>()); for(auto x: act) precalc[i].back().push_back(x); cnt = 0; } } for(auto x:act) mark[x] = false; act.clear(); } } void get_list(int x, int v, vector<int> &ans){ int pas = 0; for(int p2 = 1<<(lg2[changes[x].size()] + 1); p2 > 0; p2/=2){ if(pas + p2 < changes[x].size() && changes[x][pas + p2].time < v) pas += p2; } if(!(pas < changes[x].size() && changes[x][pas].time < v)){ return; } int lastcheck = pas / BUCKET_SIZE - 1; if(lastcheck >= 0){ for(auto a: precalc[x][lastcheck]){ mark[a] ^= true; act.insert(a); } } for(int i = (lastcheck + 1) * 30; i <= pas; i++){ int val = changes[x][i].x; mark[val]^= true; if(mark[val] == false) act.erase(val); else act.insert(val); } for(auto x:act){ ans.push_back(h[x]); mark[x] = false; } act.clear(); sort(ans.begin(), ans.end()); } int question(int x, int y, int v) { vector<int> a, b; get_list(x, v, a); get_list(y, v, b); int ans = 1e9; for(int i = 0, j = 0; i < a.size() && j < b.size();){ if(a[i] < b[j]){ ans = min(ans, b[j] - a[i]); i++; } else{ ans = min(ans, a[i] - b[j]); j++; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int j = 0; j < changes[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void get_list(int, int, std::vector<int>&)':
potion.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(pas + p2 < changes[x].size() && changes[x][pas + p2].time < v)
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:65:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if(!(pas < changes[x].size() && changes[x][pas].time < v)){
      |        ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                         ~~^~~~~~~~~~
potion.cpp:95:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0, j = 0; i < a.size() && j < b.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...