Submission #172118

#TimeUsernameProblemLanguageResultExecution timeMemory
172118dennisstarStrange Device (APIO19_strange_device)C++11
15 / 100
1538 ms524292 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ryan bear #define all(V) ((V).begin()), ((V).end()) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; typedef vector<int> vim; typedef vector<ll> vlm; struct seg { ll val; seg *l, *r; seg() {val=0, l=r=NULL;} void upd(ll s, ll e, ll fr, ll re) { if (fr>re||val==(re-fr+1)) return ; if (s<=fr&&re<=e) {val=(re-fr+1); return ;} ll md=(fr+re)/2; if (s<=md) { if (!l) l=new seg(); l->upd(s, e, fr, md); } if (md+1<=e) { if (!r) r=new seg(); r->upd(s, e, md+1, re); } val=(l?l->val:0)+(r?r->val:0); } }; seg *root=new seg(); int n; ll A, B; ll l, r; int main() { scanf("%d %lld %lld", &n, &A, &B); A/=__gcd(A, B+1); if (1000000000000000000ll/B<=A) A=1000000000000000001ll; else A*=B; for (int i=0; i<n; i++) { scanf("%lld %lld", &l, &r); l--; r--; if (r-l+1>=A) { printf("%lld\n", A); return 0; } else { r=(r-l)+l%A; l%=A; if (r>=A) { root->upd(l, A-1, 0, A-1); root->upd(0, r-A, 0, A-1); } else root->upd(l, r, 0, A-1); } } printf("%lld\n", root->val); return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &n, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &l, &r); l--; r--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...