제출 #976977

#제출 시각아이디문제언어결과실행 시간메모리
976977Batorgil952이상한 기계 (APIO19_strange_device)C++14
20 / 100
2813 ms524288 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const ll N=7e6+6; struct Node{ ll l; ll r; ll vl=-1; ll vr=-1; bool al=0; bool ar=0; ll val=0; }; Node tree[N]; ll K; ll GCD(ll x, ll y){ while(x*y!=0){ if(x>y) x%=y; else y%=x; } return x+y; } void update(ll v, ll ql, ll qr){ if(tree[v].val==tree[v].r-tree[v].l+1){ return; } if(qr<tree[v].l && tree[v].r<ql){ return; } if(ql<=tree[v].l && tree[v].r<=qr){ tree[v].val=tree[v].r-tree[v].l+1; return; } ll mid=(tree[v].l+tree[v].r)/2; if(qr<=mid){ if(!tree[v].al){ if(tree[v].vl==-1){ K++; tree[v].vl=K; tree[tree[v].vl].l=tree[v].l; tree[tree[v].vl].r=mid; update(tree[v].vl, ql, qr); } else if(tree[tree[v].vl].val!=mid-tree[v].l+1){ update(tree[v].vl, ql, qr); } } } else if(mid+1<=ql){ if(!tree[v].ar){ if(tree[v].vr==-1){ K++; tree[v].vr=K; tree[tree[v].vr].l=mid+1; tree[tree[v].vr].r=tree[v].r; update(tree[v].vr, ql, qr); } else if(tree[tree[v].vr].val!=tree[v].r-mid){ update(tree[v].vr, ql, qr); } } } else if(ql<=tree[v].l){ tree[v].al=1; if(!tree[v].ar){ if(tree[v].vr==-1){ K++; tree[v].vr=K; tree[tree[v].vr].l=mid+1; tree[tree[v].vr].r=tree[v].r; update(tree[v].vr, ql, qr); } else if(tree[tree[v].vr].val!=tree[v].r-mid){ update(tree[v].vr, ql, qr); } } } else if(qr>=tree[v].r){ tree[v].ar=1; if(!tree[v].al){ if(tree[v].vl==-1){ K++; tree[v].vl=K; tree[tree[v].vl].l=tree[v].l; tree[tree[v].vl].r=mid; update(tree[v].vl, ql, qr); } else if(tree[tree[v].vl].val!=mid-tree[v].l+1){ update(tree[v].vl, ql, qr); } } } else{ if(tree[v].vl==-1){ K++; tree[v].vl=K; tree[tree[v].vl].l=tree[v].l; tree[tree[v].vl].r=mid; update(tree[v].vl, ql, qr); } else if(tree[tree[v].vl].val!=mid-tree[v].l+1){ update(tree[v].vl, ql, qr); } if(tree[v].vr==-1){ K++; tree[v].vr=K; tree[tree[v].vr].l=mid+1; tree[tree[v].vr].r=tree[v].r; update(tree[v].vr, ql, qr); } else if(tree[tree[v].vr].val!=tree[v].r-mid){ update(tree[v].vr, ql, qr); } } tree[v].val=0; if(tree[v].al==1){ tree[v].val+=(mid-tree[v].l+1); } else tree[v].val+=tree[tree[v].vl].val; if(tree[v].ar==1){ tree[v].val+=(tree[v].r-mid); } else tree[v].val+=tree[tree[v].vr].val; } ll query(ll v, ll l, ll r){ return tree[v].val; } int main(){ ll n, i, A, B, l, r, k, m, ma; scanf("%lld",&n); scanf("%lld",&A); scanf("%lld",&B); m=GCD(B+1, A); A/=m; ma=1000000000000000002; if(ma/A<B){ k=ma; } else{ k=A*B; } // cout<<k<<endl; tree[0].l=0; tree[0].r=k-1; K=0; for(i=1; i<=n; i++){ scanf("%lld",&l); scanf("%lld",&r); if(r-l+1>=k) update(0, 0, k-1); else{ if(l%k<=r%k){ update(0, l%k, r%k); } else{ update(0, l%k, k-1); update(0, 0, r%k); } } } printf("%lld\n", query(0, 0, k-1)); return 0; }

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

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