Submission #49141

#	Time	Username	Problem	Language	Result	Execution time	Memory
49141		rzbt	Poklon (COCI17_poklon)	C++14	140 / 140	683 ms	85680 KiB

poklon

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 500005
typedef long long ll;
using namespace std;
int n,q;
int niz[MAXN];
set<int> s;
map<int,int> m;

vector<int> sve[MAXN];
vector<pair<int,int>> qve[MAXN];
int res[MAXN];
int bit[MAXN];
void dodaj(int p,int x){
    for(;p<MAXN;p+=(p&(-p)))
        bit[p]+=x;
}
int zbir(int p){
    int z=0;
    for(;p>0;p-=(p&(-p)))
        z+=bit[p];
    return z;
}



int main()
{
    scanf("%d %d", &n, &q);
    for(int i=1;i<=n;i++){

        scanf("%d", niz+i);
        s.insert(niz[i]);
    }
    int ind=0;
    for(auto x:s){
        ind++;
        m.insert(mp(x,ind));
    }
    for(int i=1;i<=n;i++){
        niz[i]=m[niz[i]];
        sve[niz[i]].pb(i);
    }
    for(int i=1;i<MAXN;i++){
        sve[i].pb(MAXN-3);
        reverse(all(sve[i]));
        if(sve[i].size()<3)continue;
        dodaj(sve[i][sve[i].size()-2],1);
        dodaj(sve[i][sve[i].size()-3],-1);
    }
    for(int qqq=1;qqq<=q;qqq++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        qve[t1].pb(mp(t2,qqq));
    }
    for(int i=1;i<=n;i++){
        for(auto x:qve[i])
            res[x.second]=zbir(x.first);
        int t=niz[i];
        if(sve[t].size()<3)continue;
        dodaj(sve[t][sve[t].size()-2],-1);
        dodaj(sve[t][sve[t].size()-3],1);
        sve[t].pop_back();
        if(sve[t].size()<3)continue;
        dodaj(sve[t][sve[t].size()-2],1);
        dodaj(sve[t][sve[t].size()-3],-1);
        //printf("  %d %d\n",sve[t].size()-2,sve[t].size()-3);
    }
    for(int i=1;i<=q;i++)printf("%d\n",res[i]);

    return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", niz+i);
         ~~~~~^~~~~~~~~~~~~
poklon.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140