제출 #342712

#제출 시각아이디문제언어결과실행 시간메모리
342712NhatMinh0208이상한 기계 (APIO19_strange_device)C++17
100 / 100
1852 ms85088 KiB
/* Normie's Template v2.0 */ // Standard library in one include. #include <bits/stdc++.h> using namespace std; // ordered_set library. #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update> // AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.) //#include <atcoder/all> //using namespace atcoder; //Pragmas (Comment out these three lines if you're submitting in szkopul.) #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //File I/O. #define FILE_IN "cseq.inp" #define FILE_OUT "cseq.out" #define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout) //Fast I/O. #define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define nfio cin.tie(0);cout.tie(0) #define endl "\n" //Order checking. #define ord(a,b,c) ((a>=b)and(b>=c)) //min/max redefines, so i dont have to resolve annoying compile errors. #define min(a,b) (((a)<(b))?(a):(b)) #define max(a,b) (((a)>(b))?(a):(b)) //Constants. #define MOD (ll(998244353)) #define MAX 300001 #define mag 320 //Pairs and 3-pairs. #define p1 first #define p2 second.first #define p3 second.second #define fi first #define se second #define pii(element_type) pair<element_type,element_type> #define piii(element_type) pair<element_type,pii(element_type)> //Quick power of 2. #define pow2(x) (ll(1)<<x) //Short for-loops. #define ff(i,__,___) for(int i=__;i<=___;i++) #define rr(i,__,___) for(int i=__;i>=___;i--) //Typedefs. #define bi BigInt typedef long long ll; typedef long double ld; typedef short sh; //---------END-------// ll n,m,i,j,k,t,t1,u,v,a,b,res; ll l[1000001],r[1000001]; vector<ll> pos; vector<ll> diff; int main() { cin>>n; cin>>a>>b; for (i=1;i<=n;i++) { cin>>l[i]>>r[i]; } u=gcd(a,b+1); u=a/u; if (ll(1e18)/u<b) { for (i=1;i<=n;i++) { v+=r[i]-l[i]+1; } cout<<v; } else { t=u*b; // cout<<t<<endl; for (i=1;i<=n;i++) { u=l[i]%t; v=(r[i]+1)%t; if (r[i]-l[i]+1>=t) return cout<<t,0; else { if (u<v) { pos.push_back(u); pos.push_back(v); } else { pos.push_back(u); pos.push_back(t); pos.push_back(0); pos.push_back(v); } } } sort(pos.begin(),pos.end()); auto last=unique(pos.begin(),pos.end()); pos.erase(last,pos.end()); for (int g : pos) diff.push_back(0); for (i=1;i<=n;i++) { u=l[i]%t; v=(r[i]+1)%t; // cout<<u<<' '<<v<<endl; if (r[i]-l[i]+1>=t) return cout<<t,0; else { if (u<v) { a=lower_bound(pos.begin(),pos.end(),u)-pos.begin(); diff[a]++; a=lower_bound(pos.begin(),pos.end(),v)-pos.begin(); diff[a]--; } else { a=lower_bound(pos.begin(),pos.end(),u)-pos.begin(); diff[a]++; a=lower_bound(pos.begin(),pos.end(),t)-pos.begin(); diff[a]--; a=lower_bound(pos.begin(),pos.end(),0)-pos.begin(); diff[a]++; a=lower_bound(pos.begin(),pos.end(),v)-pos.begin(); diff[a]--; } } } ll cur=0; for (i=0;i<pos.size();i++) { cur+=diff[i]; // cout<<cur<<' '<<i<<' '<<pos[i]<<endl; if ((cur)and(i<pos.size()-1)) res+=pos[i+1]-pos[i]; } cout<<res; } }

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

strange_device.cpp:20: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   20 | #pragma comment(linker, "/stack:200000000")
      | 
strange_device.cpp: In function 'int main()':
strange_device.cpp:118:12: warning: unused variable 'g' [-Wunused-variable]
  118 |   for (int g : pos) diff.push_back(0);
      |            ^
strange_device.cpp:148:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for (i=0;i<pos.size();i++)
      |            ~^~~~~~~~~~~
strange_device.cpp:152:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    if ((cur)and(i<pos.size()-1)) res+=pos[i+1]-pos[i];
      |                 ~^~~~~~~~~~~~~
#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...