結果
問題 | No.686 Uncertain LIS |
ユーザー | chocorusk |
提出日時 | 2018-12-21 12:22:57 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 2,588 bytes |
コンパイル時間 | 1,448 ms |
コンパイル使用メモリ | 100,028 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-11-30 22:35:18 |
合計ジャッジ時間 | 6,665 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 224 ms
8,960 KB |
testcase_10 | AC | 214 ms
8,448 KB |
testcase_11 | AC | 135 ms
6,816 KB |
testcase_12 | AC | 7 ms
5,248 KB |
testcase_13 | AC | 70 ms
5,376 KB |
testcase_14 | AC | 112 ms
6,016 KB |
testcase_15 | AC | 73 ms
5,248 KB |
testcase_16 | AC | 194 ms
8,064 KB |
testcase_17 | AC | 270 ms
9,728 KB |
testcase_18 | AC | 265 ms
9,600 KB |
testcase_19 | AC | 261 ms
9,600 KB |
testcase_20 | AC | 259 ms
9,472 KB |
testcase_21 | AC | 258 ms
9,728 KB |
testcase_22 | AC | 132 ms
9,600 KB |
testcase_23 | AC | 130 ms
9,728 KB |
testcase_24 | AC | 166 ms
9,600 KB |
testcase_25 | AC | 163 ms
9,728 KB |
testcase_26 | AC | 117 ms
9,600 KB |
testcase_27 | AC | 169 ms
9,728 KB |
testcase_28 | AC | 171 ms
9,600 KB |
testcase_29 | AC | 172 ms
9,472 KB |
testcase_30 | AC | 168 ms
9,728 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 123 ms
9,728 KB |
testcase_33 | AC | 120 ms
9,600 KB |
testcase_34 | AC | 262 ms
9,600 KB |
testcase_35 | AC | 262 ms
9,600 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> using namespace std; typedef long long int ll; typedef pair<int, int> P; random_device rnd; mt19937 mt(rnd()); uniform_real_distribution<> rnd1(0, 1.0); struct node_t{ int val; node_t *lch; node_t *rch; double pri; int cnt; int lazy_val; bool lazy; node_t() {} node_t(int v, double p):val(v), pri(p), cnt(1), lazy_val(0), lazy(false), lch(nullptr), rch(nullptr){} }; int count(node_t *t){ return !t ? 0 : t->cnt; } void push(node_t *t){ if(!t) return; if(t->lazy){ t->val+=t->lazy_val; if(t->lch){ t->lch->lazy=true; t->lch->lazy_val+=t->lazy_val; } if(t->rch){ t->rch->lazy=true; t->rch->lazy_val+=t->lazy_val; } t->lazy_val=0; t->lazy=false; } } node_t *update(node_t *t){ push(t); push(t->lch); push(t->rch); t->cnt=count(t->lch)+count(t->rch)+1; return t; } node_t *merge(node_t *l, node_t *r){ if(!l || !r) return !l ? r : l; update(l); update(r); if(l->pri > r->pri){ l->rch=merge(l->rch, r); return update(l); }else{ r->lch=merge(l, r->lch); return update(r); } } pair<node_t*, node_t*> split(node_t *t, int v){ //[0, v), [v, inf) if(!t) return make_pair(nullptr, nullptr); update(t); if(v <= t->val){ pair<node_t*, node_t*> s=split(t->lch, v); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair<node_t*, node_t*> s=split(t->rch, v); t->rch=s.first; return make_pair(update(t), s.second); } } pair<node_t*, node_t*> split2(node_t *t, int k){ //[0, k), [k,n) if(!t) return make_pair(nullptr, nullptr); update(t); if(k <= count(t->lch)){ pair<node_t*, node_t*> s=split2(t->lch, k); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair<node_t*, node_t*> s=split2(t->rch, k-1-count(t->lch)); t->rch=s.first; return make_pair(update(t), s.second); } } node_t *query(node_t *t, int l, int r){ pair<node_t*, node_t*> s=split(t, l); pair<node_t*, node_t*> s2=split(s.second, r); if(s2.first){ s2.first->lazy=true; s2.first->lazy_val=1; } pair<node_t*, node_t*> s3=split2(s2.second, 1); return merge(s.first, merge(new node_t(l, rnd1(mt)), merge(s2.first, s3.second))); } int main() { int n; cin>>n; node_t *s=nullptr; for(int i=0; i<n; i++){ int l, r; cin>>l>>r; s=query(s, l, r); } cout<<count(s)<<endl; return 0; }