| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 632822 |
2022-08-20T21:46:47 Z |
MohammadAghil |
LIS (INOI20_lis) |
C++17 |
|
2 ms |
596 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, sq = 2000, lg = 20, 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 fen[maxn], n, pos[maxn], val[maxn], dp[maxn], tmp[maxn];
set<int> val_pos[sq], place[sq];
int main(){ IOS();
cin >> n;
rep(i,1,n+1){
fen[i] = i&-i;
}
map<int, int> cmp;
rep(i,0,n){
cin >> pos[i] >> tmp[i];
cmp[tmp[i]] = 0;
}
int id = 0;
for(auto&c: cmp) c.ss = id++;
per(i,n-1,0) {
int ps = 0, cr = pos[i];
per(i,lg-1,0){
if((ps|(1<<i)) < n && fen[ps|(1<<i)] < cr){
ps |= 1<<i;
cr -= fen[ps];
}
}
ps++;
// er(nw);
val[ps] = cmp[tmp[i]];
pos[i] = ps;
for(; ps < n + 1; ps += ps&-ps) fen[ps]--;
}
// 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,0,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(*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 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
