제출 #966879

#제출 시각아이디문제언어결과실행 시간메모리
966879antonThe Potion of Great Power (CEOI20_potion)C++17
100 / 100
720 ms72108 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> typedef complex<int> point; const int INF = 1e9; int dist(vector<int>& a, vector<int>& b){ if(a.size() == 0 || b.size() == 0){ return INF; } int ia =0, ib = 0; int res= abs(a[0]-b[0]); while(ia<a.size()-1 || ib<b.size()-1){ if(ia==a.size()-1){ ib++; } else if(ib==b.size()-1){ ia++; } else if(a[ia]<=b[ib]){ ia++; } else{ ib++; } res = min(res, abs(a[ia]-b[ib])); } return res; } struct Event{ int date; vector<int> list; int change; Event(int t,int v): date(t), change(v){}; Event(int t, vector<int> v): date(t){ list =v; }; }; vector<int> apply(vector<int>& a, vector<int>&ev){ sort(ev.begin(), ev.end()); vector<int> res; auto add =[&](int v){ if(res.size()>0 && res.back() == v){ res.pop_back(); } else{ res.push_back(v); } }; int aid = 0; int eid = 0; while(aid<a.size() || eid<ev.size()){ if(eid>=ev.size()){ add(a[aid]); aid++; } else if(aid>=a.size()){ add(ev[eid]); eid++; } else{ if(a[aid]<=ev[eid]){ add(a[aid]); aid++; } else{ add(ev[eid]); eid++; } } } return res; } vector<vector<int>> vs; vector<int> h; set<pii> cur; vector<vector<Event>> events; vector<vector<int>> backed_up; vector<int> order; vector<int> redir; int n; const int TR = 10; void init(int N, int D, int H[]) { n = N; vs.resize(N); h.resize(N); events.resize(N); backed_up.resize(N); redir.resize(n); order.resize(n); for(int i = 0; i<N; i++){ h[i] = H[i]; order[i] = i; } auto cmp =[&](int a, int b){ return h[a]<h[b]; }; sort(order.begin(),order.end(), cmp); sort(h.begin(), h.end()); for(int i = 0; i<n; i++){ redir[order[i]] = i; } } void curseChanges(int U, int A[], int B[]) { for(int i = 0; i<n; i++){ events[i].push_back(Event(0, vector<int>())); } auto p_event = [&](int id,int t, int ev){ backed_up[id].push_back(ev); if(backed_up[id].size()==TR){ events[id].push_back(Event(t, apply(events[id][events[id].size()-TR].list,backed_up[id]))); backed_up[id].clear(); } else{ events[id].push_back(Event(t, ev)); } }; for(int i = 0; i<U; i++){ int a= redir[A[i]], b= redir[B[i]]; if(cur.find({a, b})!=cur.end()){ cur.erase({a, b}); } else if(cur.find({b, a})!=cur.end()){ cur.erase({b, a}); } else{ cur.insert({a, b}); } p_event(a, i+1, b); p_event(b, i+1, a); } } int get_last(int id, int t){ int cur= 0; for(int step = (1<<18); step>=1; step/=2){ if(cur+step<events[id].size()){ if(events[id][cur+step].date<=t){ cur+=step; } } } return cur; } vector<int> reconstruct(int id, int eid){ Event base = events[id][(eid/TR) * TR]; vector<int> others; for(int i = 1; i<=eid%TR; i++){ others.push_back(events[id][(eid/TR) * TR + i].change); } return apply(base.list, others); } int question(int x, int y, int v) { x= redir[x]; y= redir[y]; auto xm =reconstruct(x, get_last(x, v)); auto ym = reconstruct(y, get_last(y, v)); for(int& e: xm){ e= h[e]; } for(int& e: ym){ e= h[e]; } return dist(xm, ym); } /* int H[1000*1000]; int A[1000*1000]; int B[1000*1000]; signed main(){ int N, D, U, Q; std::cin >> N >> D >> U >> Q; for(int i = 0; i<N; i++){ cin>>H[i]; } init(N, D, H); for(int i = 0; i<U; i++){ cin>>A[i]; cin>>B[i]; } curseChanges(U, A, B); for(int i= 0; i<Q; i++){ int a, b, v; cin>>a>>b>>v; cout<<question(a, b, v)<<endl; } } */

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

potion.cpp: In function 'int dist(std::vector<int>&, std::vector<int>&)':
potion.cpp:17:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(ia<a.size()-1 || ib<b.size()-1){
      |           ~~^~~~~~~~~~~
potion.cpp:17:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(ia<a.size()-1 || ib<b.size()-1){
      |                            ~~^~~~~~~~~~~
potion.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(ia==a.size()-1){
      |            ~~^~~~~~~~~~~~
potion.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         else if(ib==b.size()-1){
      |                 ~~^~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> apply(std::vector<int>&, std::vector<int>&)':
potion.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(aid<a.size() || eid<ev.size()){
      |           ~~~^~~~~~~~~
potion.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(aid<a.size() || eid<ev.size()){
      |                           ~~~^~~~~~~~~~
potion.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if(eid>=ev.size()){
      |            ~~~^~~~~~~~~~~
potion.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         else if(aid>=a.size()){
      |                 ~~~^~~~~~~~~~
potion.cpp: In function 'int get_last(int, int)':
potion.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         if(cur+step<events[id].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...