oj.uz

Submission #873656

# Submission time Handle Problem Language Result Execution time Memory
873656 2023-11-15T12:46:03 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 1079 ms 67784 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

#define tof_io  ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define double  long double
#define int     long long
#define pb      push_back

#define all(x)  x.begin(),x.end()
#define endl    '\n'
#define sz(x) 	x.size()
//const int mod = 998244353; //998244353 1e9+7 1e9+9
const int N = 1e6 + 23;	
const int lg = 23;
const int inf = 2e18;
int fac[N];
int inv[N];
int a[N];
int ans = 0;
//int  dnt_pow	(int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
//void dnt_bld	(){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
//int  dnt_ncr	(int r,int n){if(r>n) return 0; return fac[n] * inv[r] % mod * inv[n-r] % mod;}
pair<int, int> pr[N], in[N];
int ar[N];
int lef[N];
struct Fenwick 
{
    int tree[2 * N];
 
    int get_sum(int x) 
	{
        ++x;
        int sum = 0;
        for (int i = x; i; i -= i & (-i)) 
		{
            sum += tree[i - 1];
        }
        return sum;
    }
 
    void update(int x, int v) 
	{
        ++x;
        for (int i = x; i <= N; i += i & (-i)) 
		{
            tree[i - 1] += v;
        }
    }
 
    int lower_bound(int val) 
	{
        int st = 0;
        for (int sz = N >> 1; sz; sz >>= 1)
            if (val > tree[st + sz - 1])
                val -= tree[(st += sz) - 1];
        return st;
    }
} fenwick;
 
 
int32_t main() 
{
	int n, q;
    cin >> n >> q;
    map<int, int> mp;
    for (int i = 0; i < n; i++) 
	{
        cin >> ar[i];
        auto it = mp.find(ar[i]);
        if (it == mp.end()) 
		{
            lef[i] = -1;
        } 
		else 
		{
            lef[i] = mp[ar[i]];
        }
        mp[ar[i]] = i;
    }
 
    for (int i = 0; i < q; i++) 
	{
        cin >> pr[i].second >> pr[i].first;
        in[i].first = --pr[i].first;
        in[i].second = --pr[i].second;
    }
 
    sort(pr, pr + q);
    int qind = 0;
    map<int, int> cnt;
    map<pair<int, int>, int> res;
 
    for (int i = 0; i < n; i++) 
	{
        cnt[ar[i]]++;
        if (cnt[ar[i]] == 2) 
		{
            fenwick.update(0, 1);
            fenwick.update(lef[i]+1, -1);
        } 
		else if (cnt[ar[i]] > 2) 
		{
            fenwick.update(lef[lef[lef[i]]] + 1, -1);
            fenwick.update(lef[lef[i]] + 1, +1);
 
            fenwick.update(lef[lef[i]] + 1, 1);
            fenwick.update(lef[i] + 1, -1);
        }
        while (pr[qind].first == i) 
		{
            res[pr[qind]] = fenwick.get_sum(pr[qind].second);
            qind++;
        }
    }
    for (int i = 0; i < q; i++) 
	{
        cout << res[in[i]] << endl;
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 7 ms 12892 KB Output is correct
5 Correct 126 ms 21180 KB Output is correct
6 Correct 122 ms 21180 KB Output is correct
7 Correct 318 ms 36320 KB Output is correct
8 Correct 544 ms 46792 KB Output is correct
9 Correct 790 ms 57132 KB Output is correct
10 Correct 1079 ms 67784 KB Output is correct