oj.uz

Submission #49141

# Submission time Handle Problem Language Result Execution time Memory
49141 2018-05-22T17:56:04 Z rzbt Poklon (COCI17_poklon) C++14
140 / 140
 683 ms 85680 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 39672 KB Output is correct
2 Correct 56 ms 39704 KB Output is correct
3 Correct 85 ms 39704 KB Output is correct
4 Correct 82 ms 39956 KB Output is correct
5 Correct 168 ms 45172 KB Output is correct
6 Correct 179 ms 46588 KB Output is correct
7 Correct 348 ms 53784 KB Output is correct
8 Correct 500 ms 63152 KB Output is correct
9 Correct 647 ms 73736 KB Output is correct
10 Correct 683 ms 85680 KB Output is correct