oj.uz

Submission #446937

# Submission time Handle Problem Language Result Execution time Memory
446937 2021-07-24T01:07:34 Z jamezzz None (KOI18_matrix) C++17
100 / 100
 2682 ms 239980 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 200005

struct node{
	int s,e,m;
	node *l,*r;
	set<ii> st;
	
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;st.insert(ii(-1,0));
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	
	void up(int x,ii pr){
		st.insert(pr);
		auto it=st.find(pr);
		
		if(prev(it)->se>=pr.se){
			st.erase(it);
		}
		else{
			while(next(it)!=st.end()&&next(it)->se<=pr.se){
				st.erase(next(it));
			}
		}
		
		if(s==e)return;
		if(x<=m)l->up(x,pr);
		else r->up(x,pr);
	}
	
	int qry(int x,int y,int v){
		if(s==x&&e==y){
			auto it=st.upper_bound(ii(v,-1));
			return (--it)->se;
		}
		if(y<=m)return l->qry(x,y,v);
		if(x>m)return r->qry(x,y,v);
		return max(l->qry(x,m,v),r->qry(m+1,y,v));
	}
}*root=new node(0,maxn);

int r,n,a[maxn][3],pos[maxn];
vector<int> v;

int main(){
	sf("%d%d",&r,&n);
	for(int i=0;i<n;++i)sf("%d",&a[i][0]);
	for(int i=0;i<n;++i)sf("%d",&a[i][1]);
	for(int i=0;i<n;++i)if(r==3)sf("%d",&a[i][2]);
	
	for(int j=0;j<3;++j){
		v.clear();
		for(int i=0;i<n;++i)v.pb(a[i][j]);
		sort(all(v));v.erase(unique(all(v)),v.end());
		for(int i=0;i<n;++i)a[i][j]=lower_bound(all(v),a[i][j])-v.begin()+1;
	}
	for(int i=0;i<n;++i)pos[i]=i;
	sort(pos,pos+n,[&](int i,int j){return a[i][0]<a[j][0];});
	
	for(int i=0;i<n;++i){
		int x=a[pos[i]][1],y=(r==2?i:a[pos[i]][2]);
		root->up(x,ii(y,root->qry(0,x-1,y)+1));
	}
	
	pf("%d\n",root->qry(0,maxn,INF));
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:85:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  sf("%d%d",&r,&n);
      |    ^
matrix.cpp:86:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  for(int i=0;i<n;++i)sf("%d",&a[i][0]);
      |                        ^
matrix.cpp:87:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  for(int i=0;i<n;++i)sf("%d",&a[i][1]);
      |                        ^
matrix.cpp:88:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  for(int i=0;i<n;++i)if(r==3)sf("%d",&a[i][2]);
      |                                ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 60740 KB Output is correct
2 Correct 81 ms 60324 KB Output is correct
3 Correct 86 ms 60416 KB Output is correct
4 Correct 86 ms 60616 KB Output is correct
5 Correct 89 ms 60676 KB Output is correct
6 Correct 93 ms 65756 KB Output is correct
7 Correct 90 ms 61636 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 59824 KB Output is correct
2 Correct 91 ms 60672 KB Output is correct
3 Correct 89 ms 59588 KB Output is correct
4 Correct 96 ms 59128 KB Output is correct
5 Correct 87 ms 59488 KB Output is correct
6 Correct 98 ms 65860 KB Output is correct
7 Correct 92 ms 59476 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 60740 KB Output is correct
2 Correct 81 ms 60324 KB Output is correct
3 Correct 86 ms 60416 KB Output is correct
4 Correct 86 ms 60616 KB Output is correct
5 Correct 89 ms 60676 KB Output is correct
6 Correct 93 ms 65756 KB Output is correct
7 Correct 90 ms 61636 KB Output is correct
8 Correct 2272 ms 156780 KB Output is correct
9 Correct 1590 ms 149488 KB Output is correct
10 Correct 1018 ms 136548 KB Output is correct
11 Correct 484 ms 83120 KB Output is correct
12 Correct 1155 ms 141008 KB Output is correct
13 Correct 1281 ms 235324 KB Output is correct
14 Correct 1020 ms 134228 KB Output is correct
15 Correct 484 ms 83252 KB Output is correct
16 Correct 1308 ms 239980 KB Output is correct
17 Correct 1295 ms 235316 KB Output is correct
18 Correct 1092 ms 156696 KB Output is correct
19 Correct 987 ms 131240 KB Output is correct
20 Correct 2682 ms 158680 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 59824 KB Output is correct
2 Correct 91 ms 60672 KB Output is correct
3 Correct 89 ms 59588 KB Output is correct
4 Correct 96 ms 59128 KB Output is correct
5 Correct 87 ms 59488 KB Output is correct
6 Correct 98 ms 65860 KB Output is correct
7 Correct 92 ms 59476 KB Output is correct
8 Correct 1103 ms 110476 KB Output is correct
9 Correct 710 ms 80288 KB Output is correct
10 Correct 1194 ms 133880 KB Output is correct
11 Correct 1382 ms 236856 KB Output is correct
12 Correct 563 ms 79936 KB Output is correct
13 Correct 1118 ms 115076 KB Output is correct
14 Correct 1227 ms 113288 KB Output is correct
15 Correct 1378 ms 223824 KB Output is correct
16 Correct 1402 ms 223636 KB Output is correct
17 Correct 708 ms 79948 KB Output is correct
18 Correct 2311 ms 105988 KB Output is correct
19 Correct 919 ms 79968 KB Output is correct
20 Correct 1119 ms 111028 KB Output is correct
21 Correct 1388 ms 224464 KB Output is correct
22 Correct 2182 ms 113132 KB Output is correct
23 Correct 727 ms 79684 KB Output is correct
24 Correct 925 ms 79668 KB Output is correct
25 Correct 1646 ms 114724 KB Output is correct
26 Correct 905 ms 79800 KB Output is correct
27 Correct 566 ms 79848 KB Output is correct
28 Correct 1381 ms 224436 KB Output is correct
29 Correct 720 ms 79612 KB Output is correct
30 Correct 695 ms 79544 KB Output is correct
31 Correct 882 ms 79588 KB Output is correct
32 Correct 726 ms 79600 KB Output is correct