Submission #1302072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302072		Bzslayed	Poklon (COCI17_poklon)	C++20	140 / 140	482 ms	12940 KiB

poklon

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    
#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"
#define fi first
#define se second

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int blk = 707;
bool cmp(pair<pii, int>&i, pair<pii, int>&j){
    ll fblk = i.fi.fi/blk, sblk = j.fi.fi/blk;
    if (fblk == sblk) return i.fi.second < j.fi.second;
    else return fblk < sblk;
}

int n, q;
int a[500005], dis[500005], ans[500005];
int occ[500005];
int curans = 0;

void discr(){
    vector<int> unq_v;
    unq_v.reserve(n);
    for (int i=1; i<=n; i++) unq_v.push_back(a[i]);
    sort(unq_v.begin(), unq_v.end());
    unq_v.erase(unique(unq_v.begin(), unq_v.end()), unq_v.end());
    for (int i=1; i<=n; i++) dis[i] = lower_bound(unq_v.begin(), unq_v.end(), a[i])-unq_v.begin()+1;
}

inline void add(int x){
    occ[dis[x]]++;
    if (occ[dis[x]] == 2) curans++;
    else if (occ[dis[x]] == 3) curans--;
}
 
inline void sub(int x){
    occ[dis[x]]--;
    if (occ[dis[x]] == 2) curans++;
    else if (occ[dis[x]] == 1) curans--;
}

int l = 1, r = 0;
void advance(int ql, int qr){
	while (r < qr) add(++r);
	while (l > ql) add(--l);
	while (l < ql) sub(l++);
	while (r > qr) sub(r--);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i=1; i<=n; i++) cin >> a[i];
    discr();
    pair<pii, int> qry[q];
    for (int i=0; i<q; i++) cin >> qry[i].fi.fi >> qry[i].fi.se, qry[i].se = i;
    sort(qry, qry+q, cmp);

    for (int i=0; i<q; i++){
        auto [p, idx] = qry[i];
        auto [ql, qr] = p;
        advance(ql, qr);
        ans[idx] = curans;
    }

    for (int i=0; i<q; i++) cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 140 / 140