Submission #764143

#	Time	Username	Problem	Language	Result	Execution time	Memory
764143		vjudge1	Exam (eJOI20_exam)	C++17	0 / 100	13 ms	13864 KiB

exam

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define len(x) (int)x.size()
#define ull unsigned long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define int long long

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
int n,a[N],b[N],sp[30][N],ans,lg[N];
vector <pair<int,int>> q;
vector <int> g[N];
set <int> st;
map <int,int> mp;

main(){
	// freopen("txt.in", "r", stdin);
	// freopen("txt.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		st.insert(a[i]);
	}
	for (int i=1;i<=n;i++){
		cin >> b[i];
		st.insert(b[i]);
	}
	int cnt = 0;
	for (auto it : st){
		mp[it] = ++cnt;
	}
	for (int i=1;i<=n;i++){
		a[i] = mp[a[i]];
		g[a[i]].pb(i);
	}
	for (int i=1;i<=n;i++){
		b[i] = mp[b[i]];
	}
	lg[2] = 1;
	for (int i=2;i<=n;i++){
		if (!lg[i]){
			lg[i] = lg[i-1];
		}
		lg[i*2] = lg[i] + 1;
	}
	for (int i=1;i<=n;i++){
		sp[0][i] = a[i];
	}
	for (int j=1;j<=20;j++){
		for (int i=1;i<=n;i++){
			sp[j][i] = max(sp[j-1][i], sp[j-1][i+(1<<(j-1))]);
		}
	}
	for (int i=1;i<=n;i++){
		if (b[i] < a[i]){
			q.pb({b[i], i});
		}
		if (b[i]==a[i]){
			ans++;
		}
	}
	sort(q.begin(), q.end());
	for (int i=0;i<len(q);i++){
		int l = 0;
		int r = len(g[q[i].F]) - 1;
		while(l<=r){
			int md = (l + r) / 2;
			if (g[q[i].F][md] < q[i].S){
				l = md + 1;
			}
			else{
				r = md - 1;
			}
		}
		if (l>=0 && l<len(g[q[i].F])){
			int ln = (i - g[q[i].F][l] + 1);
			int x = lg[ln];
			if (q[i].F == max(sp[x][g[q[i].F][l]], sp[x][i - (1<<x) + 1])){
				ans++;
				continue;
			}
		}
		if (r>=0 && r<len(g[q[i].F])){
			int ln = (g[q[i].F][r] - i + 1);
			int x = lg[ln];
			if (q[i].F == max(sp[x][i], sp[x][g[q[i].F][r]-(1<<x)+1])){
				ans++;
			}
		}
	}
	cout << ans;
}

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)

//a/b%mod = a*(b^(m-2)%mod)
//(a>>x)&1 == 0
//a^b = (a+b)-2(a&b)

//srand(time(0))-always changing

Compilation message (stderr)

exam.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22