Submission #380422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
380422	2021-03-21T17:03:32 Z	SavicS	Poklon (COCI17_poklon)	C++14	140 / 140	1579 ms	45420 KB

poklon

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 500005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;
ll niz[maxn];

vector<pii> upit[maxn];

int cnt[maxn];
int last[maxn];
int pre[maxn];
int jos[maxn];

int res[maxn];

map<ll,int> ind;

ll dud1[maxn];
void upd1(int x, ll val){
	while(x <= maxn){
		dud1[x] += val;
		x += x&(-x);
	}
}
ll query1(int x){
	ll sum = 0;
	while(x > 0){
		sum += dud1[x];
		x -= x&(-x);
	}
	return sum;
}

ll dud2[maxn];
void upd2(int x, ll val){
	while(x <= maxn){
		dud2[x] += val;
		x += x&(-x);
	}
}
ll query2(int x){
	ll sum = 0;
	while(x > 0){
		sum += dud2[x];
		x -= x&(-x);
	}
	return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
	cin >> n >> q;
	ff(i,1,n){
		cin >> niz[i];
		ind[niz[i]] = 0;
	}
	int br = 0;
	for(auto& c : ind)c.se = ++br;
	
	ff(i,1,n)niz[i] = ind[niz[i]];
		
	ff(i,1,q){
		int l, r;
		cin >> l >> r;
		upit[r].pb({l, i});
	}
	
	ff(i,1,n){
		int x = niz[i];
		cnt[x] += 1;
		if(cnt[x] >= 2){
			if(pre[x] != 0){
				upd1(pre[x], -1);
			}
			if(jos[x] != 0){
				upd2(jos[x], -1);
			}
			
			upd1(last[x], 1);
			if(pre[x] != 0)upd2(pre[x], 1);
			
			jos[x] = pre[x];
			pre[x] = last[x];
			
		}
		last[x] = i;
		for(auto c : upit[i]){
			int l = c.fi;
			int id = c.se;
			res[id] = query1(i) - query1(l - 1) - (query2(i) - query2(l - 1));
		}
	}
	ff(i,1,q)cout << res[i] << endl;
    return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	12268 KB	Output is correct
2	Correct	10 ms	12288 KB	Output is correct
3	Correct	12 ms	12268 KB	Output is correct
4	Correct	22 ms	12524 KB	Output is correct
5	Correct	285 ms	18540 KB	Output is correct
6	Correct	293 ms	18668 KB	Output is correct
7	Correct	608 ms	25452 KB	Output is correct
8	Correct	932 ms	32352 KB	Output is correct
9	Correct	1261 ms	38892 KB	Output is correct
10	Correct	1579 ms	45420 KB	Output is correct