oj.uz

Submission #330322

# Submission time Handle Problem Language Result Execution time Memory
330322 2020-11-24T19:13:05 Z errorgorn None (KOI18_matrix) C++17
100 / 100
 2852 ms 306112 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;
int arr[200005][3];
int proc[200005];

struct node{
	int s,e,m;
	set<ii> st;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		st.insert(ii(-1,0));
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,ii val){
		auto it=st.insert(val).fi;
		
		if ((*prev(it)).se>=val.se){
			st.erase(it);
		}
		else{
			while (next(it)!=st.end() && (*next(it)).se<=val.se){
				st.erase(next(it));
			}
		}
		
		if (s==e) return;
		if (i<=m) l->update(i,val);
		else r->update(i,val);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			return (*--st.upper_bound(ii(k,-1))).se;
		}
		else if (j<=m) return l->query(i,j,k);
		else if (m<i) return r->query(i,j,k);
		else return max(l->query(i,m,k),r->query(m+1,j,k));
	}
} *root=new node(0,200005);

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m;
	
	rep(x,0,n){
		rep(y,0,m){
			cin>>arr[y][x];
		}
	}
	rep(y,0,m) proc[y]=y;
	
	sort(proc,proc+m,[](int i,int j){
		return arr[i][0]<arr[j][0];
	});
	
	rep(x,1,3){
		vector<int> temp;
		rep(y,0,m) temp.push_back(arr[y][x]);
		sort(all(temp));
		map<int,int> id;
		rep(y,0,m) id[temp[y]]=y+1;
		rep(y,0,m) arr[y][x]=id[arr[y][x]];
	}
	
	rep(x,0,m){
		int a=arr[proc[x]][1],b=(n==2?x:arr[proc[x]][2]);
		//cout<<a<<" "<<b<<endl;
		root->update(a,ii(b,root->query(0,a-1,b)+1));
	}
	
	cout<<root->query(0,200005,1e9);
}

Compilation message

matrix.cpp: In constructor 'node::node(int, int)':
matrix.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 68204 KB Output is correct
2 Correct 91 ms 67564 KB Output is correct
3 Correct 95 ms 67692 KB Output is correct
4 Correct 92 ms 68036 KB Output is correct
5 Correct 102 ms 68204 KB Output is correct
6 Correct 105 ms 74860 KB Output is correct
7 Correct 94 ms 69228 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 66796 KB Output is correct
2 Correct 102 ms 68332 KB Output is correct
3 Correct 105 ms 66668 KB Output is correct
4 Correct 105 ms 66156 KB Output is correct
5 Correct 99 ms 66668 KB Output is correct
6 Correct 113 ms 75200 KB Output is correct
7 Correct 110 ms 66796 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 68204 KB Output is correct
2 Correct 91 ms 67564 KB Output is correct
3 Correct 95 ms 67692 KB Output is correct
4 Correct 92 ms 68036 KB Output is correct
5 Correct 102 ms 68204 KB Output is correct
6 Correct 105 ms 74860 KB Output is correct
7 Correct 94 ms 69228 KB Output is correct
8 Correct 2718 ms 189208 KB Output is correct
9 Correct 1887 ms 179540 KB Output is correct
10 Correct 1010 ms 162380 KB Output is correct
11 Correct 536 ms 91212 KB Output is correct
12 Correct 1249 ms 168268 KB Output is correct
13 Correct 1300 ms 293888 KB Output is correct
14 Correct 1025 ms 159180 KB Output is correct
15 Correct 542 ms 91212 KB Output is correct
16 Correct 1295 ms 300140 KB Output is correct
17 Correct 1291 ms 293936 KB Output is correct
18 Correct 1100 ms 189256 KB Output is correct
19 Correct 993 ms 155060 KB Output is correct
20 Correct 2852 ms 191688 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 66796 KB Output is correct
2 Correct 102 ms 68332 KB Output is correct
3 Correct 105 ms 66668 KB Output is correct
4 Correct 105 ms 66156 KB Output is correct
5 Correct 99 ms 66668 KB Output is correct
6 Correct 113 ms 75200 KB Output is correct
7 Correct 110 ms 66796 KB Output is correct
8 Correct 1178 ms 137232 KB Output is correct
9 Correct 911 ms 97100 KB Output is correct
10 Correct 1270 ms 168520 KB Output is correct
11 Correct 1519 ms 306112 KB Output is correct
12 Correct 738 ms 96972 KB Output is correct
13 Correct 1188 ms 143708 KB Output is correct
14 Correct 1349 ms 141260 KB Output is correct
15 Correct 1469 ms 288772 KB Output is correct
16 Correct 1509 ms 288728 KB Output is correct
17 Correct 924 ms 97120 KB Output is correct
18 Correct 2500 ms 131660 KB Output is correct
19 Correct 1103 ms 97228 KB Output is correct
20 Correct 1219 ms 138596 KB Output is correct
21 Correct 1505 ms 289996 KB Output is correct
22 Correct 2353 ms 141432 KB Output is correct
23 Correct 885 ms 97100 KB Output is correct
24 Correct 1120 ms 96976 KB Output is correct
25 Correct 1787 ms 143640 KB Output is correct
26 Correct 1070 ms 97100 KB Output is correct
27 Correct 738 ms 96988 KB Output is correct
28 Correct 1507 ms 290252 KB Output is correct
29 Correct 861 ms 97224 KB Output is correct
30 Correct 912 ms 96988 KB Output is correct
31 Correct 1082 ms 97100 KB Output is correct
32 Correct 896 ms 96972 KB Output is correct