Submission #24732

#	Time	Username	Problem	Language	Result	Execution time	Memory
24732		toonewbie	Poklon (COCI17_poklon)	C++14	0 / 140	1773 ms	33500 KiB

poklon

/*
ID: barish21
LANG: C++14
TASK: test
*/

/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();

const intt max1 = 11;
const intt max2 = 102;
const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 500005;
const intt max6 = 1000006;
const intt max7 = 10000007;
const intt lg2 = 7;
const intt lg3 = 10;
const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;
const intt lg7 = 24;
const intt lg8 = 27;
const intt lg9 = 30;
const intt lg18 = 60;
const intt INF = 2LL * 1000000000;
/***************/

/***Additional Functions***/
intt powmod(intt a,intt b,intt mod){intt res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
intt gcd(intt a, intt b) { while(b) b ^= a ^= b ^= a %= b; return a;}
intt lcm(intt a,intt b){return a*b/gcd(a,b);}
intt is_prime(intt n){if(n==1)return 0;if(n==2)return 1;if(n%2==0)return 0;for(intt i=3;i<=sqrt(n);i+=2)if(n%i==0)return 0;return 1;}
intt is_integer(double n){if(floor(n)==ceil(n))return 1;return 0;}

intt sto_int(string s){stringstream ss(s);intt n;ss>>n;return n;}
string to_string(intt n){stringstream ss;ss<<n;string s=ss.str();return s;}
/**************************/

struct data {
    intt l, r;
    intt idx;
};

intt n, q, arr[maxx];
pair <intt, intt> brr[maxx];
data query[maxx];
intt D;

bool cmp (data a, data b) {
    if (a.r / D == b.r / D)
        return a.l < b.l;
    return a.r < b.r;
}

intt cnt[maxx], ans = 0;

void add (intt i) {
    cnt[arr[i]] ++;
    if (cnt[arr[i]] == 2)
        ans ++;
    if (cnt[arr[i]] == 3)
        ans --;
}

void del (intt i) {
    cnt[arr[i]] --;
    if (cnt[arr[i]] == 2)
        ans ++;
    if (cnt[arr[i]] == 1)
        ans --;
}
intt ansv[maxx];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    IO;
    cin >> n >> q;
    D = sqrt (n);
    for (intt i = 1; i <= n; i++)
        cin >> arr[i], brr[i].first = arr[i], brr[i].second = i;
    sort (brr + 1, brr + n + 1);
    brr[0].first = 0;
    intt ptr = 0;
    for (intt i = 1; i <= n; i++) {
        if (brr[i].first != brr[i - 1].first)
            ptr ++;
        arr[brr[i].second] = ptr;
    }
    for (intt i = 1; i <= q; i++)
        cin >> query[i].l >> query[i].r, query[i].idx = i;
    sort (query + 1, query + q + 1, cmp);
    query[0].l = query[1].l, query[0].r = query[1].l - 1;
    for (intt i = 1; i <= q; i++) {
        intt l1 = query[i - 1].l, r1 = query[i - 1].r;
        intt l2 = query[i].l, r2 = query[i].r;
        for (intt j = l1 + 1; j <= l2; j++)
            add (j);
        for (intt j = r1 + 1; j <= r2; j++)
            add (j);
        for (intt j = l1; j > l2; j--)
            del (j);
        for (intt j = r1; j > r2; j--)
            del (j);
        ansv[query[i].idx] = ans;
    }
    for (intt i = 1; i <= q; i++)
        cout << ansv[i] << endl;
    return 0;
}

• Subtask 1: 0 / 140