結果
問題 | No.674 n連勤 |
ユーザー | nmnmnmnmnmnmnm |
提出日時 | 2017-03-27 21:42:33 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 2,162 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 103,052 KB |
実行使用メモリ | 12,780 KB |
最終ジャッジ日時 | 2023-10-12 13:14:13 |
合計ジャッジ時間 | 5,368 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,020 KB |
testcase_01 | AC | 2 ms
4,860 KB |
testcase_02 | AC | 3 ms
4,836 KB |
testcase_03 | AC | 3 ms
4,912 KB |
testcase_04 | AC | 3 ms
4,952 KB |
testcase_05 | AC | 2 ms
4,840 KB |
testcase_06 | AC | 3 ms
4,816 KB |
testcase_07 | AC | 2 ms
4,912 KB |
testcase_08 | AC | 2 ms
4,956 KB |
testcase_09 | AC | 2 ms
4,824 KB |
testcase_10 | AC | 3 ms
4,816 KB |
testcase_11 | AC | 10 ms
5,744 KB |
testcase_12 | AC | 9 ms
5,468 KB |
testcase_13 | AC | 52 ms
5,756 KB |
testcase_14 | AC | 101 ms
12,732 KB |
testcase_15 | AC | 95 ms
12,780 KB |
testcase_16 | AC | 119 ms
12,608 KB |
testcase_17 | AC | 117 ms
12,676 KB |
testcase_18 | AC | 98 ms
10,780 KB |
testcase_19 | AC | 129 ms
12,664 KB |
ソースコード
#include <algorithm> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iostream> #include <map> #include <memory> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(ll i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define ctos(c) string(1,c) #define print(x) cout<<#x<<" = "<<x<<endl; #define MOD 1000000007 #define A 250 ll dh[60300]; ll dl[60300]; ll dd[60300]; ll dddh[300]; ll dddl[300]; ll geth(ll p){ ll index = p/A; if(dddh[index]==-1){ return dh[p]; } else{ return dddh[index]; } } ll getl(ll p){ ll index = p/A; if(dddl[index]==-1){ return dl[p]; } else{ return dddl[index]; } } int main(){ ll n,q; cin>>n>>q; clr(dh,-1); clr(dl,-1); clr(dd,-1); clr(dddh,-1); clr(dddl,-1); set<ll> se; vector<pair<ll,ll> > vp; rep(i,0,q){ ll a,b; cin>>a>>b; a++;b++; vp.pb(mp(a,b)); se.insert(a); se.insert(b); } vector<ll> vse(all(se)); map<ll,ll> ma; rep(i,0,vse.sz){ dd[i+1]=vse[i]; ma[vse[i]] = i+1; } vector<pair<ll,ll> > vp1; rep(i,0,vp.sz){ vp1.pb(mp(ma[vp[i].fi],ma[vp[i].se])); } ll mx = 0; rep(i,0,vp1.sz){ ll a1,b1; ll a = vp1[i].fi; ll b = vp1[i].se; ll pa = getl(a-1); if(pa==-1)a1 = a; else { if(dd[a]-1<=dd[geth(a-1)]){ a1 = pa; } else{ a1 = a; } } ll pb = geth(b+1); if(pb==-1)b1 = b; else { if(dd[getl(b+1)]<=dd[b]+1){ b1 = pb; } else{ b1 = b; } } ll index1 = a1/A; ll index2 = b1/A; rep(j,index1*A,(index1+1)*A){ if(a1 <= j && j <= b1){ dl[j] = a1; dh[j] = b1; } } rep(j,index2*A,(index2+1)*A){ if(a1 <= j && j <= b1){ dl[j] = a1; dh[j] = b1; } } rep(j,index1+1,index2){ dddl[j] = a1; dddh[j] = b1; } mx = max(mx,dd[b1]-dd[a1]+1); printf("%lld\n", mx); } return 0; }