oj.uz

Submission #518773

# Submission time Handle Problem Language Result Execution time Memory
518773 2022-01-24T15:00:47 Z aloo123 Poklon (COCI17_poklon) C++14
140 / 140
 2300 ms 20852 KB 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert
#define pf push_front
#define pb push_back

// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto &a : x)

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;     // not too close to LLONG_MAX

#define int ll
const int xd[8] = {1, 0, -1, 0, -1,-1,1,1}, yd[8] = {0, 1, 0, -1,-1,1,-1,1}; // for every grid problem!!
const int N = 5e5+5;
const int LOGN = 25;
const int BLOCKSZ = 350;

using namespace std;
int a[N];
struct query{
    int l,r,idx;
};
query Q[N];

bool cmp(query x, query y){
    return mp(x.l/BLOCKSZ, x.r) < mp(y.l/BLOCKSZ, y.r);
}
int freq[N];
int ans = 0;
int fans[N];
void add(int x){
    freq[a[x]]++;
    if(freq[a[x]] == 2) ans++;
    if(freq[a[x]] == 3) ans--;
}
void rem(int x){
    freq[a[x]]--;
    if(freq[a[x]] == 2) ans++;
    if(freq[a[x]] == 1) ans--;
}

void solve(){
    int n, q;
    cin >>n >> q;
    for(int i =0;i<n;i++)cin>>a[i];
   
   ////
    set<int> s;
    for(int i =0;i<n;i++)s.ins(a[i]);
    vl v;
    for(int i:s) v.pb(i);
    map<int,int>m;
    for(int i = 0;i<sz(v);i++){
        m[v[i]] = i + 1;
    }
    for(int i =0;i<n;i++){
        a[i] = m[a[i]];
    }
///////

    for(int i =1;i<=q;i++){
        cin >> Q[i].l>> Q[i].r;Q[i].idx=i;
        Q[i].l--;
        Q[i].r--;
    }
    sort(Q+1,Q+q+1,cmp);

    int cur_l= 0, cur_r = -1;
    for(int i = 1;i <=q;i++){
        while(cur_l>Q[i].l){
            cur_l--;
            add(cur_l);
        }
        while(cur_r < Q[i].r){
            cur_r++;
            add(cur_r);
        }
        while(cur_l<Q[i].l){
            rem(cur_l);
            cur_l++;
        }
        while(cur_r>Q[i].r){
            rem(cur_r);
            cur_r--;
        }
        fans[Q[i].idx] = ans;
    }
    for(int i= 1;i<=q;i++){
        cout<<fans[i]<<"\n";
    }








}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin>>t;
    while (t--){
        solve();
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 556 KB Output is correct
5 Correct 186 ms 4376 KB Output is correct
6 Correct 153 ms 4380 KB Output is correct
7 Correct 516 ms 8604 KB Output is correct
8 Correct 965 ms 12712 KB Output is correct
9 Correct 1558 ms 16836 KB Output is correct
10 Correct 2300 ms 20852 KB Output is correct