| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 632815 |
2022-08-20T21:30:11 Z |
MohammadAghil |
LIS (INOI20_lis) |
C++17 |
|
416 ms |
1048576 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e6 + 5, lg = 30, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int seg[maxn<<2], n, pos[maxn], val[maxn], dp[maxn], tmp[maxn];
set<int> val_pos[maxn], place[maxn];
void build(int x = 1, int lx = 0, int rx = n){
if(lx + 1 == rx){
seg[x] = 1;
return;
}
int mid = (lx + rx)>>1;
build(x<<1, lx, mid);
build(x<<1|1, mid, rx);
seg[x] = rx - lx;
}
int get(int k, int x = 1, int lx = 0, int rx = n){
seg[x]--;
if(lx + 1 == rx){
return lx;
}
int mid = (lx + rx)>>1;
if(seg[x<<1] < k) return get(k - seg[x<<1], x<<1|1, mid, rx);
return get(k, x<<1, lx, mid);
}
int main(){ IOS();
cin >> n;
build();
rep(i,0,n){
cin >> pos[i] >> tmp[i];
}
per(i,n-1,0) {
int nw = get(pos[i]);
// er(nw);
val[nw] = tmp[i];
pos[i] = nw;
}
// rep(i,0,n) er(pos[i], val[i]);
int ans = 1;
rep(i,0,n){
int p = pos[i], v = val[pos[i]];
dp[p] = 1;
rep(j,1,v){
auto it = lower_bound(all(val_pos[j]), p);
if(it != begin(val_pos[j])){
dp[p] = max(dp[p], dp[*prev(it)] + 1);
// er(i, j);
}
}
// er(i, dp[p]);
ans = max(ans, dp[p]);
place[dp[p]].insert(p);
val_pos[v].insert(p);
// auto bg = place[dp[p]].upper_bound(p), en = bg;
// for(; en != end(place[dp[pos[i]]]) && val[*en] > v; en++) dp[*en]++, ans = max(ans, dp[p] + 1), er(i, *en, val[*en], v);
// place[dp[p] + 1].insert(bg, en);
// place[dp[p]].erase(bg, en);
// rep(i,1,5){
// cerr << i << ":" << endl;
// for(int c: place[i]) cerr << c << ' ';
// cerr << endl;
// }
// cerr << "_____" << endl;
vector<int> stk{p};
while(sz(stk)){
int r = stk.back(); stk.pop_back();
auto bg = place[dp[r]].upper_bound(r);
auto en = bg;
for(; en != end(place[dp[r]]) && val[*en] > val[r]; en++){
dp[*en]++;
ans = max(ans, dp[r] + 1);
stk.pb(*en);
}
place[dp[r] + 1].insert(bg, en);
place[dp[r]].erase(bg, en);
}
cout << ans << '\n';
}
return 0-0;
}
Compilation message
Main.cpp: In function 'void IOS()':
Main.cpp:19:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
416 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
416 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
