제출 #873626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873626		vjudge1	Poklon (COCI17_poklon)	C++17	140 / 140	314 ms	55444 KiB

poklon

#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 / 140