Submission #24741

#	Time	Username	Problem	Language	Result	Execution time	Memory
24741		toonewbie	Poklon (COCI17_poklon)	C++14	140 / 140	2213 ms	17716 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 int max2 = 102;
const int max3 = 1003;
const int max4 = 10004;
const int maxx = 500005;
const int max6 = 1000006;
const int max7 = 10000007;
const int lg2 = 7;
const int lg3 = 10;
const int lg4 = 13;
const int lg5 = 17;
const int lg6 = 20;
const int lg7 = 24;
const int lg8 = 27;
const int lg9 = 30;
const int lg18 = 60;
const int INF = 2LL * 1000000000;
/***************/

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

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

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

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

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

int cnt[maxx], ans = 0;

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

void del (int i) {
    cnt[arr[i]] --;
    if (cnt[arr[i]] == 2)
        ans ++;
    if (cnt[arr[i]] == 1)
        ans --;
}
int 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 (int i = 1; i <= n; i++)
        scanf ("%d", &arr[i]), brr[i].first = arr[i], brr[i].second = i;
    sort (brr + 1, brr + n + 1);
    brr[0].first = 0;
    int ptr = 0;
    for (int i = 1; i <= n; i++) {
        if (brr[i].first != brr[i - 1].first)
            ptr ++;
        arr[brr[i].second] = ptr;
    }
    for (int i = 1; i <= q; i++)
        scanf ("%d%d", &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 (int i = 1; i <= q; i++) {
        int l1 = query[i - 1].l, r1 = query[i - 1].r;
        int l2 = query[i].l, r2 = query[i].r;
        for (int j = l1 - 1; j >= l2; j--)
            add (j);
        for (int j = r1 + 1; j <= r2; j++)
            add (j);
        for (int j = l1; j < l2; j++)
            del (j);
        for (int j = r1; j > r2; j--)
            del (j);
        ansv[query[i].idx] = ans;
    }
    for (int i = 1; i <= q; i++)
        printf ("%d\n", ansv[i]);
    return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:97:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &arr[i]), brr[i].first = arr[i], brr[i].second = i;
                                                                        ^
poklon.cpp:107:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d", &query[i].l, &query[i].r), query[i].idx = i;
                                                                   ^

• Subtask 1: 140 / 140