oj.uz

답안 #676504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676504 2022-12-31T03:52:05 Z penguin133 Poklon (COCI17_poklon) C++17
140 / 140
 1210 ms 92068 KB 
#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

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

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 7 ms 1248 KB Output is correct
5 Correct 165 ms 18332 KB Output is correct
6 Correct 163 ms 18348 KB Output is correct
7 Correct 439 ms 36948 KB Output is correct
8 Correct 775 ms 55392 KB Output is correct
9 Correct 963 ms 73732 KB Output is correct
10 Correct 1210 ms 92068 KB Output is correct