結果
問題 | No.686 Uncertain LIS |
ユーザー |
![]() |
提出日時 | 2018-12-08 23:40:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 552 ms / 2,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 805 ms |
コンパイル使用メモリ | 44,212 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 22:26:06 |
合計ジャッジ時間 | 5,195 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <stdio.h> #include <algorithm> using namespace std; const int maxs = 100; int c,g[1010][maxs*2+1],s[1010],p[1010],r[100010]; void just() { int n = 0; for (int i=0;i<c;i++){ for (int j=0;j<s[i];j++){ r[n++] = g[i][j] + p[i]; } } c = (n + maxs - 1) / maxs; for (int i=0;i<c;i++) s[i] = p[i] = 0; for (int i=0;i<n;i++){ g[i/maxs][i%maxs] = r[i]; s[i/maxs]++; } } void del(int i, int v) { s[i]--; for (int j=v;j<s[i];j++) g[i][j] = g[i][j+1]; } void rem(int y) { for (int i=0;i<c;i++) if (s[i]){ if (y <= g[i][s[i]-1] + p[i]){ for (int v=0;v<s[i];v++){ if (y <= g[i][v] + p[i]){ del(i,v); if (s[i] == 0) just(); return; } } } } } void add(int x, int y) { for (int i=0;i<c;i++) if (s[i]){ int a = g[i][0] + p[i]; int b = g[i][s[i]-1] + p[i]; if (x <= a && b <= y) p[i]++; else if (max(x,a) <= min(b,y)){ for (int v=0;v<s[i];v++){ int &a = g[i][v]; a += p[i]; if (x <= a && a <= y) a++; } p[i] = 0; } } } void mak(int i, int v) { for (int j=s[i];j>v;j--) g[i][j] = g[i][j-1]; s[i]++; } void ins(int x) { if (c == 0){ g[0][0] = x; s[0] = 1; p[0] = 0; c = 1; return; } for (int i=0;i<c;i++){ if (x <= g[i][s[i]-1] + p[i] || i == c-1){ int v = 0; while (v < s[i] && x > g[i][v] + p[i]) v++; mak(i,v); g[i][v] = x - p[i]; if (s[i] == maxs*2) just(); break; } } } int main() { int N; scanf ("%d",&N); while (N--){ int x,y; scanf ("%d %d",&x,&y); rem(y); add(x,y); ins(x); } int ans = 0; for (int i=0;i<c;i++) ans += s[i]; printf ("%d\n",ans); return 0; }