oj.uz

Submission #833032

# Submission time Handle Problem Language Result Execution time Memory
833032 2023-08-21T20:03:55 Z vjudge1 Exam (eJOI20_exam) C++14
39 / 100
 328 ms 99148 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define rep(i,n,N) for(int i = n; i<=N; ++i)
#define rap(i,n,N) for(int i = n; i>=N; --i)
#define For(i,n,N) for(int i = n; i< N; ++i)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define mems(x,y) memset(x,y,sizeof x)
#define ari(x) array<int,x>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
const int MAX = 1e5 + 5;
mt19937 rng(time(NULL));

int n,x[MAX],y[MAX],cnt,dp2[5005][5005],dp[205][205][205][2];
vector<int> v,a,b;
bool vis[MAX],gg;
int pf[205][205];

int g(int nw,int val){
	val = max(nw, val);
	if(val>n || nw>n)return 0;
	int &ret = dp2[nw][val];
	if(ret!=-1)return ret;
	return ret = max(g(nw+1,val) + (y[nw]==val), g(nw, val+1));
}

int f(int le,int ri,int val,bool st){
	if(le>ri || val>n)return 0;
	int &ret = dp[le][ri][val][st];
	if(ret!=-1)return ret;
	ret = max({f(le+1,ri,val,st), f(le,ri-1,val,st), f(le,ri,val+1,0)});
	if(!st && pf[val][ri]-pf[val][le-1])ret = max(ret, f(le,ri,val,1));
	
	if(st){// val ada
		if(x[le]<=val && y[le]==val)ret = max(ret, f(le+1,ri,val,st) + 1);
		if(x[ri]<=val && y[ri]==val)ret = max(ret, f(le,ri-1,val,st) + 1);
	}
	
	return ret;
}

#define lc (id<<1)
#define rc ((id<<1)|1)

struct rmqSegtree{
	int tree[1<<18];
	int n,a,b;
	void build(int id,int le,int ri){
		if(le==ri){
			tree[id] = x[le];
			return;
		}
		int mid = le+ri>>1;
		build(lc,le,mid), build(rc,mid+1,ri);
		tree[id] = max(tree[lc], tree[rc]);
		return;
	}
	int que(int id,int le,int ri){
		if(le>b || ri<a)return 0;
		if(le>=a && ri<=b)return tree[id];
		int mid = le+ri>>1;
		return max(que(lc,le,mid), que(rc,mid+1,ri));
	}
	int que(int L,int R){
		a = L, b = R;
		return que(1,1,n);
	}
}rmq;

struct ansSegtree{
	int tree[1<<18];
	int n,val,a,b;
	void upd(int id,int le,int ri){
		if(le==ri){
			tree[id] = val;
			return;
		}
		int mid = le+ri>>1;
		if(a<=mid)upd(lc,le,mid);
		else upd(rc,mid+1,ri);
		tree[id] = max(tree[lc], tree[rc]);
		return;
	}
	int que(int id,int le,int ri){
		if(le>b || ri<a)return 0;
		if(le>=a && ri<=b)return tree[id];
		int mid = le+ri>>1;
		return max(que(lc,le,mid), que(rc,mid+1,ri));
	}
	int que(int L,int R){
		a = L, b = R;
		return que(1,1,n);
	}
	void upd(int pos,int _v){
		a = pos;
		val = _v;
		upd(1,1,n);
	}
}tree[2];

int z[MAX];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	rep(i,1,n)cin>>x[i], v.pb(x[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	rep(i,1,n)x[i] = upper_bound(all(v), x[i]) - v.begin();
	auto it = v.begin();
	rep(i,1,n){
		cin>>y[i];
		it = lower_bound(all(v), y[i]);
		y[i] = it==v.end() || *it!=y[i] ? 0 : it-v.begin()+1;
	}
	
//	cout<<"____\n";
//	rep(i,1,n)cout<<x[i]<<" "; cout<<endl;
//	rep(i,1,n)cout<<y[i]<<" "; cout<<endl;
	
	x[0] = x[n+1] = v.size()+1;
	
	bool tc2 = 1;
	rep(i,2,n)if(y[i]!=y[i-1])tc2 = 0;
	if(tc2){
		gg = 0;
		rep(i,1,n){
			if(x[i]==y[i])gg = 1;
			else if(x[i]>y[i])gg = 0;
			vis[i]|= gg;
		}
		gg = 0;
		rap(i,n,1){
			if(x[i]==y[i])gg = 1;
			else if(x[i]>y[i])gg = 0;
			vis[i]|= gg;
			cnt+= vis[i];
		}
		cout<<cnt<<endl;
		return 0;
	}
	
	bool tc3 = 1;
	rep(i,1,n)if(x[i]!=i)tc3 = 0;
	if(tc3){
		mems(dp2, -1);
		cout<<g(1,1)<<endl;
		return 0;
	}
	
	bool tc4 = v.size()==n;
	if(tc4){
		rmq.n = tree[0].n = tree[1].n = n;
		rmq.build(1,1,n);
		rep(i,1,n)z[x[i]] = i;
		int pos;
		rep(i,1,n)if(x[i]<=y[i]){
			pos = z[y[i]];
			if(pos>i){
				if(rmq.que(i,pos)!=y[i])continue;
				tree[0].upd(y[i], max(tree[0].que(1,y[i]), tree[1].tree[1]) + 1);
			}
			else {
				if(rmq.que(pos,i)!=y[i])continue;
				tree[1].upd(y[i], tree[1].que(y[i],n) + 1);
			}
		}
		cout<<max(tree[0].tree[1], tree[1].tree[1])<<endl;
		return 0;
	}
	
	if(n<=10){
		rep(i,1,n){
			rep(j,1,n)pf[j][i] = pf[j][i-1];
			pf[x[i]][i]++;
		}
		mems(dp, -1);
		cout<<f(1,n,1,0)<<endl;
		return 0;
	}
	return 1;
	
	return 0;
}

Compilation message

exam.cpp: In member function 'void rmqSegtree::build(int, int, int)':
exam.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In member function 'int rmqSegtree::que(int, int, int)':
exam.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In member function 'void ansSegtree::upd(int, int, int)':
exam.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In member function 'int ansSegtree::que(int, int, int)':
exam.cpp:96:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In function 'int main()':
exam.cpp:160:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |  bool tc4 = v.size()==n;
      |             ~~~~~~~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 24 ms 67776 KB Output is correct
3 Correct 24 ms 67672 KB Output is correct
4 Correct 23 ms 67672 KB Output is correct
5 Correct 26 ms 67700 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 18 ms 2644 KB Output is correct
4 Correct 10 ms 2036 KB Output is correct
5 Correct 35 ms 3660 KB Output is correct
6 Correct 12 ms 2028 KB Output is correct
7 Correct 18 ms 2192 KB Output is correct
8 Correct 34 ms 3548 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 98304 KB Output is correct
2 Correct 33 ms 98356 KB Output is correct
3 Correct 66 ms 98688 KB Output is correct
4 Correct 305 ms 99112 KB Output is correct
5 Correct 319 ms 99132 KB Output is correct
6 Correct 328 ms 99148 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 24 ms 67776 KB Output is correct
3 Correct 24 ms 67672 KB Output is correct
4 Correct 23 ms 67672 KB Output is correct
5 Correct 26 ms 67700 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Runtime error 0 ms 340 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 24 ms 67776 KB Output is correct
3 Correct 24 ms 67672 KB Output is correct
4 Correct 23 ms 67672 KB Output is correct
5 Correct 26 ms 67700 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 32 ms 98304 KB Output is correct
8 Correct 33 ms 98356 KB Output is correct
9 Correct 66 ms 98688 KB Output is correct
10 Correct 305 ms 99112 KB Output is correct
11 Correct 319 ms 99132 KB Output is correct
12 Correct 328 ms 99148 KB Output is correct
13 Runtime error 0 ms 340 KB Execution failed because the return code was nonzero
14 Halted 0 ms 0 KB -