oj.uz

Submission #988648

# Submission time Handle Problem Language Result Execution time Memory
988648 2024-05-25T11:25:30 Z ibsha Poklon (COCI17_poklon) C++17
140 / 140
 660 ms 29476 KB 
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD ((1ull << 59) - 1)
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>

//__int128 fastpow(ll base,ll exp){__int128 result=1;while (exp){if (exp%2==1) result*=base;exp/=2;base*=base;}return result;}

ull fastpow(ull base, ull exp) {
    ull res = 1;
    while (exp) {
        if (exp & 1)
            res *= base;
        base *= base;
        res%=MOD;
        base%=MOD;
        exp >>= 1;
    }

    return res;
}

bool cmp(pair<pll,pll> i, pair<pll,pll> j){
    //if (i.first == j.second) return i.first < j.first;
    return i.first.second < j.first.second;
}
bool cmp2(pair<pll,pll> i, pair<pll,pll> j){
    //if (i.first == j.second) return i.first < j.first;
    return i.second.first < j.second.first;
}

ll l,r;
ll idx=1;
struct tree{

        vector<ll> seg;
        ll out = 0;

        void ini(ll n){
            while (idx < n) idx*=2;
            seg.resize(idx*2, out);
        }

        ll op(ll i, ll j){
            return i+j;
        }

        void build() { // Unused.
            for (int i = idx - 1;i > 0;i--) {
                seg[i] = op(seg[i * 2] , seg[i * 2 + 1]);
            }
        }

        void update(int i, ll x=1) { // 1 based i
            i += idx;
            i--; // Cause of this, remove for 0 based i
            seg[i] = x;
            while (i) {
                i /= 2;
                seg[i] = op(seg[i * 2], seg[i * 2 + 1]);
            }
        }

        // [inclusive, inclusive] and 1 based, just call calc(); when l and r are defined.
        ll calc(ll s = 1, ll e = idx, ll node = 1) {
            if (r < s || e < l)
                return out;
            if (l <= s and e <= r)
                return seg[node];
            ll mid = (s + e) / 2;
            return op(calc(s, mid, node * 2) , calc(mid + 1, e, node * 2 + 1));
        }
};

void solve() {
    //cout << fixed << setprecision(6);
    ll n; cin >> n; ll q; cin >> q;
    ll arr[n+2];
    for (int i=1;i<=n;i++) cin >> arr[i];
    pair<pll,pll> qs[q];
    for (int i=0;i<q;i++){
        cin >> qs[i].first.first >> qs[i].first.second;
        qs[i].second.first = i;
        qs[i].second.second=707;
    }
    sort(qs,qs+q,cmp);
    map<ll, deque<ll> > mp;
    tree s;
    s.ini(n);
    ll curi=0;
    for (auto& p : qs){
        while (curi < p.first.second){
            curi++;
            mp[arr[curi]].push_back(curi);
            //cout << curi;
            if (mp[arr[curi]].size() > 3) {
                s.update(mp[arr[curi]][0],0);
                mp[arr[curi]].pop_front();
            }
            if (mp[arr[curi]].size() == 3){
                s.update(mp[arr[curi]][0],-1);
                s.update(mp[arr[curi]][1],1);
                s.update(mp[arr[curi]][2],0);
            }
            else if (mp[arr[curi]].size() == 2){
                s.update(mp[arr[curi]][0],1);
                s.update(mp[arr[curi]][1],0);
            }
            else s.update(mp[arr[curi]][0],0);
        }
        l = p.first.first; r = p.first.second;
        p.second.second = s.calc();
    }
    sort(qs,qs+q,cmp2);
    for (auto& p : qs) cout << p.second.second << endl;
}



signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    //freopen("auxiliary.in","r",stdin);
    //freopen("auxiliary.out","w",stdout);
    ll t=1;
    //cin >> t;
    for (int i=1; i<=t; i++){
        //cout << "Case " << i << ": \n";
        solve();
        cout << endl;
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 832 KB Output is correct
5 Correct 91 ms 6468 KB Output is correct
6 Correct 95 ms 6736 KB Output is correct
7 Correct 257 ms 13144 KB Output is correct
8 Correct 405 ms 21608 KB Output is correct
9 Correct 520 ms 25552 KB Output is correct
10 Correct 660 ms 29476 KB Output is correct