# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
432021 | 2021-06-17T19:11:18 Z | ak2006 | Temperature (POI11_tem) | C++14 | 52 ms | 65540 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define lc 2 * no #define rc 2 * no + 1 void setIO() { fast; #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } int n = 1e6 + 5; vi a(n),b(n),l2(n); vvi dp(n,vi(21)); void build() { l2[1] = 0,dp[1][0] = a[1]; for (int i = 2;i<=n;i++)l2[i] = l2[i/2] + 1,dp[i][0] = a[i]; for (int i = n;i>=1;i--) for (int j = 1;(1<<j) + i <= n;j++) dp[i][j] = max(dp[i][j - 1],dp[i + (1<<(j - 1))][j - 1]); } int MAX(int l,int r) { int len = l2[r - l + 1]; return max(dp[l][len],dp[r - (1<<len) + 1][len]); } int search(int i) { //binary search for the smallest j such that MAX(1,1,n,j,i) <= b[i] int l = 1,r = i,pos = i; while (l <= r){ int mid = (l + r)/2; if (MAX(mid,i) <= b[i]){ pos = mid; r = mid - 1; } else l = mid + 1; } return pos; } int main() { setIO(); cin>>n; for (int i = 1;i<=n;i++)cin>>a[i]>>b[i]; build(); int cur = search(1); int ans = 1 - cur + 1; for (int i = 2;i<=n;i++){ int val = search(i); int now = max(val,cur); ans = max(ans,i - now + 1); cur = max(cur,val); } cout<<ans; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 45 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 50 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 52 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 49 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 50 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 50 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 49 ms | 65540 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |