Submission #540381

#	Time	Username	Problem	Language	Result	Execution time	Memory
540381		avaneeshk098	Poklon (COCI17_poklon)	C++17	140 / 140	605 ms	45032 KiB

poklon

#include <bits/stdc++.h>


#define ff              first
#define int 			long long int
#define ss              second
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define max_size        100000000
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define w(t)			int t; cin >> t; while(t--)
#define inf             1e18
#define MOD				(int)1e9+7
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)      substr(a,b-a+1)
#define mina(a,b,c)		min(a, min(b, c))
#define maxa(a,b,c)		max(a, max(b, c))
#define sz(a)			(int)a.size()	
#define endl 			'\n'
#define trace(x)        cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y)		for(int i = x; i < y; i++)
// #define f(t)			int t; cin >> t; for(int i = 1; i <= t; i++)

using namespace std;

bool sortbysec(const pair<int,int> &a, const pair<int,int> &b){ return (a.ff > b.ff); } 

int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}

double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }

double min(double a, double b){if(a <= b){return a;} else{return b;	}}

struct segtree{	
	vi seg;
	int n;
	
	segtree(int m) : seg(4*m) { n = m; }
	
	int query(int l, int r, int ql, int qr, int pos){
		if(l > qr || r < ql){
			return 0;
		}
		if(l >= ql && r <= qr) return seg[pos];
		int mid = (l+r)/2;
		int m1 = query(l, mid, ql, qr, pos*2);
		int m2 = query(mid+1, r, ql, qr, pos*2+1);
		return m1+m2;
	}	
	
	int query(int l, int r){
		return query(1,n,l,r,1);	
	}
	
	void update(int l, int r, int qidx, int qval, int pos){
		if(l == r){
			seg[pos] = qval;
			return;
		}
		int mid = (l+r)/2;
		if(qidx <= mid) update(l, mid, qidx, qval, pos*2);
		else update(mid+1, r, qidx, qval, pos*2+1);
		seg[pos] = seg[pos*2] + seg[pos*2+1];
	}
	
	void update(int idx, int val){
		update(1,n, idx, val, 1);
	}
	
	void print(int l, int r, int pos) {
		cout << l << " " << r << ": " << seg[pos] << endl;
		if(l == r) return;
		int mid = (l+r)/2;
		print(l, mid, pos*2);
		print(mid+1, r, pos*2+1);
	}
	
	void print(){
		print(1,n,1);
	}
};

void solve(){
	int n, q;
	cin >> n >> q;
	vi a(n);
	segtree st(n);
	FOR(0,n) cin >> a[i];
	unordered_map<int, array<int,3>> fq;
	unordered_map<int, int> cn;
	vector<array<int,3>> queries;
	FOR(0,q){
		int l,r;
		cin >> l >> r;
		queries.pb({r,l,i});
	} 
	sort(queries.begin(), queries.end());
	vi ans(q);
	int id = 0;
	for(auto i : queries){
		auto [r,l,idx] = i;
		while(id < r){
			int curr = a[id];
			if(cn[curr] == 0){
				fq[curr][0] = id+1;
			}
			else if(cn[curr] == 1){
				st.update(fq[curr][0], 1);
				fq[curr][1] = fq[curr][0];
				fq[curr][0] = id+1;
			}
			else if(cn[curr] == 2){
				st.update(fq[curr][1], -1);
				st.update(fq[curr][0], 1);
				fq[curr][2] = fq[curr][1];
				fq[curr][1] = fq[curr][0];
				fq[curr][0] = id+1;
			}
			else if(cn[curr] > 2){
				st.update(fq[curr][2], 0);
				st.update(fq[curr][1], -1);
				st.update(fq[curr][0], 1);
				fq[curr][2] = fq[curr][1];
				fq[curr][1] = fq[curr][0];
				fq[curr][0] = id+1;
			}
			cn[curr]++;
			id++;
		}
		ans[idx] = st.query(l,r);
	}
	for(auto i : ans) cout << i << endl;
}

int32_t main(){
	FIO;
	//~ w(t){solve();}
	solve();
	//f(t){cout << "Case #" << i << ": "; solve();}
	return 0; 
}

• Subtask 1: 140 / 140