Submission #519047

#	Time	Username	Problem	Language	Result	Execution time	Memory
519047		ac2hu	Poklon (COCI17_poklon)	C++14	140 / 140	1220 ms	19492 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int block = 400;
int a[N];
int freq[N];
int ans[N];
struct queries{
    int i,l,r;
} qq[N];
int n,q;
int temp = 0;
inline void add(int i){
    if(freq[a[i]] == 2)
        temp--;
    freq[a[i]]++;
    if(freq[a[i]] == 2)
        temp++;
}
inline void remove(int i){
    if(freq[a[i]] == 2)
        temp--;
    freq[a[i]]--;
    if(freq[a[i]] == 2)
        temp++;
}
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
    cin >> n >> q;
    for(int i = 0;i<n;i++)cin >> a[i];
    for(int i = 0;i<q;i++){
        cin >> qq[i].l >> qq[i].r;
        qq[i].l--;
        qq[i].r--;
        qq[i].i = i;
    }
    sort(qq,qq + q,[&](queries a,queries b){
        int ab = a.l/block;
        int bb = b.l/block;
        if(ab == bb){
            if(ab%2 == 0)
                return a.r < b.r;
            else
                return a.r > b.r;
        }
        else 
            return ab < bb;
    });
    int l = 0,r = -1;
    for(int i = 0;i<q;i++){
        while(r < qq[i].r){
            r++;
            add(r);
        }
        while(l > qq[i].l){
            l--;
            add(l);
        }
        while(r > qq[i].r){
            remove(r);
            r--;
        }
        while(l < qq[i].l){
            remove(l);
            l++;
        }
        ans[qq[i].i] = temp;
    }
    for(int i = 0;i<q;i++)
        cout << ans[i] << "\n";
}

• Subtask 1: 140 / 140