Submission #1157895
Source Code Expand
#include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <string.h> #include <cstdlib> #include <ctime> #include <cmath> #include <map> #include <set> #include <iostream> #include <sstream> #include <numeric> #include <cctype> #include <bitset> #include <cassert> #include <random> #define fi first #define se second #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define rng(a) a.begin(),a.end() #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define pb push_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcount #define uni(x) x.erase(unique(rng(x)),x.end()) #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define df(x) int x = in() #define dame { puts("-1"); return 0;} #define show(x) cout<<#x<<" = "<<x<<endl; #define PQ(T) priority_queue<T,vector<T>,greater<T> > #define bn(x) ((1<<x)-1) #define newline puts("") using namespace std; typedef long long int ll; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<P> vp; inline int in() { int x; scanf("%d",&x); return x;} inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');} template<typename T>istream& operator>>(istream&i,const vector<T>&v) {rep(j,sz(v))i>>v[j];return i;} template<typename T>string join(const vector<T>&v) {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);} template<typename T>ostream& operator<<(ostream&o,const vector<T>&v) {if(sz(v))o<<join(v);return o;} template<typename T1,typename T2>istream& operator>>(istream&i,const pair<T1,T2>&v) {return i>>v.fi>>v.se;} template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v) {return o<<v.fi<<","<<v.se;} const int MX = 100005, INF = 1001001001; const ll LINF = 1e18; const double eps = 1e-10; // Segment tree (RMQ type) struct seg { typedef int TT; vector<TT> d; int x2; seg(){} seg(int mx) { x2 = 1; while (x2 < mx) x2 <<= 1; d.resize(x2<<1,-1); } TT get(int i) { TT res = -1; i += x2; for (;i;i>>=1) { maxs(res,d[i]); } return res; } void add(int a, int b, TT x) { return add(a,b,x,1,0,x2);} void add(int a, int b, TT x, int i, int l, int r){ if (a <= l && r <= b) { d[i] = x; return; } int c = (l+r)>>1; if (a < c) add(a,b,x,i<<1,l,c); if (c < b) add(a,b,x,i<<1|1,c,r); } }; // // coordinate compression struct X { typedef int T; vector<T> d; void add(T x) { d.pb(x);} void init() { sort(rng(d)); d.erase(unique(rng(d)), d.end()); } int size() const { return sz(d);} int operator[](int i) const { return d[i];} int operator()(T x) const { return upper_bound(rng(d),x)-d.begin()-1;} }; // int main() { int n,m; scanf("%d%d",&n,&m); vi a(n), b(n); rep(i,n) { scanf("%d%d",&a[i],&b[i]); a[i] *= 2; --b[i]; } ll ans = LINF, sum = 0; vl s(n); X xs; xs.add(0); rep(i,n) { s[i] = sum+1; sum += a[i]; xs.add(s[i]%m); xs.add(sum%m); } xs.init(); seg t(sz(xs)); vl d(n); rep(i,n) { if (b[i]) continue; if (a[i] > m) dame; int l = xs(s[i]%m); int r = xs((s[i]+a[i]-1)%m); int p = t.get(r); d[i] = 0; if (p != -1) { ll r1 = (s[i]+a[i]-1)%m; ll r2 = (s[p]+a[p]-1)%m; d[i] = d[p]+(r2+m-r1)%m; } if (l <= r) { t.add(l,r,i); } else { t.add(l,sz(xs),i); t.add(0,r,i); } } rep(i,sz(xs)) { int x = xs[i]; int p = t.get(i); if (p == -1) { ans = 0; break; } ll r2 = (s[p]+a[p]-1)%m; ll now = d[p]+(r2+m-x)%m; // cout<<i<<" "<<x<<" "<<now<<endl; mins(ans,now); } ans += sum; cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | snuke |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 4221 Byte |
Status | AC |
Exec Time | 110 ms |
Memory | 5620 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:114:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&m); ^ ./Main.cpp:117:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&a[i],&b[i]); ^
Judge Result
Set Name | Sample | All | subtask | subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | 500 / 500 | 500 / 500 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All | sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask | sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask2 | sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 2 ms | 256 KB |
in10.txt | AC | 75 ms | 5620 KB |
in101.txt | AC | 50 ms | 4596 KB |
in102.txt | AC | 48 ms | 4596 KB |
in103.txt | AC | 51 ms | 3828 KB |
in104.txt | AC | 46 ms | 5620 KB |
in105.txt | AC | 47 ms | 5620 KB |
in106.txt | AC | 50 ms | 4596 KB |
in107.txt | AC | 48 ms | 4596 KB |
in108.txt | AC | 51 ms | 3828 KB |
in109.txt | AC | 46 ms | 5620 KB |
in11.txt | AC | 77 ms | 5620 KB |
in110.txt | AC | 47 ms | 5620 KB |
in12.txt | AC | 73 ms | 5620 KB |
in13.txt | AC | 70 ms | 5620 KB |
in14.txt | AC | 73 ms | 5620 KB |
in15.txt | AC | 69 ms | 5620 KB |
in16.txt | AC | 71 ms | 5620 KB |
in17.txt | AC | 72 ms | 5620 KB |
in18.txt | AC | 73 ms | 5620 KB |
in19.txt | AC | 71 ms | 5620 KB |
in2.txt | AC | 76 ms | 5620 KB |
in20.txt | AC | 72 ms | 5620 KB |
in21.txt | AC | 52 ms | 5620 KB |
in22.txt | AC | 51 ms | 5620 KB |
in23.txt | AC | 54 ms | 5620 KB |
in24.txt | AC | 54 ms | 5620 KB |
in25.txt | AC | 32 ms | 3572 KB |
in26.txt | AC | 32 ms | 3572 KB |
in27.txt | AC | 31 ms | 3572 KB |
in28.txt | AC | 32 ms | 3444 KB |
in3.txt | AC | 74 ms | 5620 KB |
in4.txt | AC | 77 ms | 5620 KB |
in5.txt | AC | 65 ms | 5108 KB |
in6.txt | AC | 71 ms | 5620 KB |
in7.txt | AC | 66 ms | 4596 KB |
in8.txt | AC | 53 ms | 5620 KB |
in9.txt | AC | 77 ms | 5620 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |
sample4.txt | AC | 1 ms | 256 KB |
sub2in1.txt | AC | 1 ms | 256 KB |
sub2in10.txt | AC | 1 ms | 256 KB |
sub2in11.txt | AC | 1 ms | 256 KB |
sub2in12.txt | AC | 1 ms | 256 KB |
sub2in13.txt | AC | 1 ms | 256 KB |
sub2in14.txt | AC | 1 ms | 256 KB |
sub2in15.txt | AC | 1 ms | 256 KB |
sub2in16.txt | AC | 1 ms | 256 KB |
sub2in17.txt | AC | 1 ms | 256 KB |
sub2in18.txt | AC | 1 ms | 256 KB |
sub2in19.txt | AC | 1 ms | 256 KB |
sub2in2.txt | AC | 1 ms | 256 KB |
sub2in20.txt | AC | 1 ms | 256 KB |
sub2in21.txt | AC | 1 ms | 256 KB |
sub2in22.txt | AC | 1 ms | 256 KB |
sub2in23.txt | AC | 1 ms | 256 KB |
sub2in24.txt | AC | 1 ms | 256 KB |
sub2in3.txt | AC | 1 ms | 256 KB |
sub2in4.txt | AC | 1 ms | 256 KB |
sub2in5.txt | AC | 1 ms | 256 KB |
sub2in6.txt | AC | 1 ms | 256 KB |
sub2in7.txt | AC | 1 ms | 256 KB |
sub2in8.txt | AC | 1 ms | 256 KB |
sub2in9.txt | AC | 1 ms | 256 KB |
subin1.txt | AC | 110 ms | 5620 KB |
subin10.txt | AC | 100 ms | 5620 KB |
subin101.txt | AC | 87 ms | 5620 KB |
subin102.txt | AC | 65 ms | 5620 KB |
subin103.txt | AC | 60 ms | 5620 KB |
subin104.txt | AC | 61 ms | 5620 KB |
subin105.txt | AC | 54 ms | 5620 KB |
subin106.txt | AC | 58 ms | 5620 KB |
subin107.txt | AC | 69 ms | 5620 KB |
subin108.txt | AC | 73 ms | 5620 KB |
subin109.txt | AC | 65 ms | 5620 KB |
subin11.txt | AC | 94 ms | 5620 KB |
subin12.txt | AC | 98 ms | 5620 KB |
subin13.txt | AC | 99 ms | 5620 KB |
subin14.txt | AC | 99 ms | 5620 KB |
subin15.txt | AC | 97 ms | 5620 KB |
subin16.txt | AC | 99 ms | 5620 KB |
subin17.txt | AC | 91 ms | 5620 KB |
subin18.txt | AC | 94 ms | 5620 KB |
subin19.txt | AC | 96 ms | 5620 KB |
subin2.txt | AC | 103 ms | 5620 KB |
subin20.txt | AC | 97 ms | 5620 KB |
subin201.txt | AC | 1 ms | 256 KB |
subin21.txt | AC | 34 ms | 3444 KB |
subin22.txt | AC | 34 ms | 3572 KB |
subin23.txt | AC | 34 ms | 3444 KB |
subin24.txt | AC | 34 ms | 3444 KB |
subin3.txt | AC | 106 ms | 5620 KB |
subin4.txt | AC | 90 ms | 5108 KB |
subin5.txt | AC | 97 ms | 5620 KB |
subin6.txt | AC | 70 ms | 5620 KB |
subin7.txt | AC | 95 ms | 5620 KB |
subin8.txt | AC | 77 ms | 5492 KB |
subin9.txt | AC | 106 ms | 5620 KB |