Submission #676504

#	Time	Username	Problem	Language	Result	Execution time	Memory
676504		penguin133	Poklon (COCI17_poklon)	C++17	140 / 140	1210 ms	92068 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
#define int long long
int A[500005], ans[500005];
map<int, int> m, m2, m3;
pair<int, pair<int, int> > Q[500005];
struct node{
	int s,e,m,val,lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e =_e, m = s + (e-s)/2, lazy = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			val = l->val + r->val;
		}
		else val = A[s], l = r = NULL;
	}
	void propo(){
		if(lazy){
			val += lazy*(e-s+1);
			if(s != e){
				l->lazy += lazy;
				r->lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, int c){
		if(a == s && b == e){lazy += c;return;}
		else if(b <= m)l->update(a,b,c);
		else if(a > m)r->update(a,b,c);
		else l->update(a,m,c), r->update(m+1, b,c);
		l->propo(), r->propo();
		val = l->val + r->val;
	}
	int query(int a, int b){
		propo();
		if(a == s && b == e)return val;
		if(a > m)return r->query(a,b);
		else if(b <= m)return l->query(a,b);
		else return l->query(a,m) + r->query(m+1, b);
	}
}*root;
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin >> n >> q;
	root= new node(1, n);
	for(int i=1;i<=n;i++)cin >> A[i];
	for(int i=0;i<q;i++)cin >> Q[i].second.first >> Q[i].first, Q[i].second.second = i;
	sort(Q, Q+q);
	int in = 0 ;
	for(int i=1;i<=n;i++){
		int x = m[A[i]];
		int z = m2[A[i]];
		int e = m3[A[i]];
		if(x > z)root->update(z+1, x, 1);
		if(z > e)root->update(e+1, z, -1);
		while(in < q && Q[in].first == i){
			int y = root->query(Q[in].second.first, Q[in].second.first);
			ans[Q[in].second.second] = y;
			in++;
		}
		m3[A[i]] = m2[A[i]];
		m2[A[i]] = m[A[i]];
		m[A[i]] = i;
	}
	for(int i=0;i<q;i++)cout << ans[i] << '\n';
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140