oj.uz

Submission #873626

# Submission time Handle Problem Language Result Execution time Memory
873626 2023-11-15T11:57:57 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 314 ms 55444 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;

const int N = 5e5 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

struct Fen {
	int bit[N];
	
	Fen() {
		fill(bit,bit + N,0);
	}
	
	void add(int pos,int x) {
		pos ++;
		for(; pos < N; pos += pos&-pos) 
			bit[pos] += x;
	}	
	
	int get(int pos) {
		int ans=0;
		pos ++;
		for(;pos > 0; pos -= pos&-pos) 
			ans += bit[pos];
		return ans;
	}
	
	int get(int l,int r) {
		return get(r) - get(l-1);
	}

} fen;

int n,q;
int a[N];
vector<int> comp;
vector<int> inds[N];
vector<pii> Q[N];
int ans[N];
int pos[N];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q;
	for(int i = 0 ; i <n ; i++) {
		cin>>a[i];
		comp.pb(a[i]);
	}
	sort(all(comp)); comp.resize(unique(all(comp)) - comp.begin());
	for(int i = 0 ; i < n ; i++) {
		a[i] = lower_bound(all(comp),a[i]) - comp.begin();
		inds[a[i]].pb(i);
		pos[i] = sz(inds[a[i]])-1;
	}
	for(int i =0 ; i <q ; i++) {
		int l,r; cin>>l>>r;
		l--,r--;
		Q[r].pb({l,i});
	}
	
	for(int i = 0 ; i < n; i++) {
		int x = pos[i],y = a[i];
		// x-3 -> +1
		// x-2 -> -2
		// x-1 -> +1
		if(x-3 >= 0) {
			fen.add( inds[y][x-3],1);
		}
		if(x-2 >= 0) {
			fen.add(inds[y][x-2],-2);
		}
		if(x-1 >= 0) {
			fen.add(inds[y][x-1],1);	
		}
		for(auto [l,id] : Q[i]) {
			ans[id] = fen.get(l,i);
		}
	}
	for(int i = 0 ; i < q; i++) cout<<ans[i] << '\n';
	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 6 ms 31576 KB Output is correct
3 Correct 6 ms 31580 KB Output is correct
4 Correct 8 ms 31836 KB Output is correct
5 Correct 50 ms 36024 KB Output is correct
6 Correct 59 ms 36184 KB Output is correct
7 Correct 126 ms 41164 KB Output is correct
8 Correct 167 ms 46484 KB Output is correct
9 Correct 224 ms 51116 KB Output is correct
10 Correct 314 ms 55444 KB Output is correct