Submission #446937

#	Time	Username	Problem	Language	Result	Execution time	Memory
446937		jamezzz	조화행렬 (KOI18_matrix)	C++17	100 / 100	2682 ms	239980 KiB

matrix

#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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62