Submission #249050

#TimeUsernameProblemLanguageResultExecution timeMemory
249050crossing0verStrange Device (APIO19_strange_device)C++17
100 / 100
633 ms23960 KiB
#include<bits/stdc++.h> #define tm (tl + tr)/2 #define inf 1100000000000000000 #define ll long long using namespace std; struct tre{ bool lazy; ll sum; ll L,R; tre() { lazy = sum = L = R = 0; } }; vector<tre>t(1); void push(ll v,ll tl,ll tr,ll L,ll R) { if (t[v].lazy) { t[L].lazy = t[R].lazy = 1; t[L].sum = tm - tl+1; t[R].sum = tr - tm; t[v].lazy = 0; } } void upd(ll v,ll tl,ll tr,ll l,ll r) { if (l > tr || r < tl || t[v].lazy) return; if (l <= tl && r >= tr) { t[v].lazy = 1; t[v].sum = tr - tl + 1; return; } if (t[v].L == 0) { t[v].L = t.size(); t.push_back(tre()); } if (t[v].R == 0) { t[v].R = t.size(); t.push_back(tre()); } push(v,tl,tr,t[v].L,t[v].R); upd(t[v].L,tl,tm,l,r); upd(t[v].R,tm+1,tr,l,r); t[v].sum = t[ t[v].L ].sum + t[ t[v].R ].sum; } main() { ios::sync_with_stdio(false); ll n,a,b; cin >> n >> a >> b; ll m = a/(__gcd(a,b+1)); if (m > inf/b) m = inf; else m*=b; vector<pair<ll,ll> > v; for (ll l,r;n--;) { cin >> l >> r; if (r - l + 1 >= m) { cout << m <<'\n'; exit(0); } l%=m; r%=m; if (l < 0) l+=m; if (r < 0) r+=m; if ( l <= r) { v.push_back({l,r}); // upd(0,0,m-1,l,r); } else { v.push_back({0,r}); v.push_back({l,m-1}); // upd(0,0,m-1,l,m-1); // upd(0,0,m-1,0,r); } } sort(v.begin(),v.end()); ll st = 0, en = -1,ans = 0; for (auto i : v) { ll x = i.first, y =i.second; if (y <= en) continue; if (x > en) { ans += y - x + 1; st = x; en = y; } else { ans += y - en; st = x; en = y; } } cout << ans; }

Compilation message (stderr)

strange_device.cpp: In constructor 'tre::tre()':
strange_device.cpp:12:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   lazy = sum = L = R = 0;
          ~~~~^~~~~~~~~~~
strange_device.cpp: At global scope:
strange_device.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:79:5: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  ll st = 0, en = -1,ans = 0;
     ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...