Submission #1256213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256213		nanaseyuzuki	Poklon (COCI17_poklon)	C++20	140 / 140	1429 ms	11004 KiB

poklon

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <-- (modified: added trace output)
    I love Nanasaki Ai ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<ll, int>
#define ll long long int
using namespace std;

const int mn = 5e5 + 5, block = 3085;
const int inf = 1e18;

int n, q;
int a[mn];
int freq[mn];
int cnt = 0, sum = 0;

struct qr{
    int l, r, id, ans;
    bool operator < (const qr &other) const {
        if ((l / block) != (other.l / block))
            return (l / block) < (other.l / block);
        return r < other.r;
    }
}query[500005];

bool cmp(qr a, qr b){
    return a.id < b.id;
}

void add(int pos){
    if(freq[a[pos]] == 2){
        cnt--;
    }
    freq[a[pos]]++;
    if(freq[a[pos]] == 2){
        cnt++;
    }
}

void del(int pos){
    if(freq[a[pos]] == 2){
        cnt--;
    }
    freq[a[pos]] --;
    if(freq[a[pos]] == 2){
        cnt++;
    }
}

int curl, curr;
void xltv(int l, int r){
    while(curl < l){
        del(curl);
        curl ++;
    }
    while(curl > l){
        curl --;
        add(curl);
    }
    while(curr > r){
        del(curr);
        curr--;
    }
    while(r > curr){
        curr++;
        add(curr);
    }
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int max1 = 0;
    for(int i = 1; i <= q; i++){
        cin >> query[i].l >> query[i].r;
        max1 = max({max1, query[i].l, query[i].r});
        query[i].id = i;
    }
    sort(query + 1, query + q + 1);
    curl = query[1].l, curr = query[1].r;
    for(int i = curl; i <= curr; i++){
        freq[a[i]] ++;
        if(freq[a[i]] == 2) cnt ++;
        else if(freq[a[i]] == 3) cnt --;
    }
    query[1].ans = cnt;
    for(int i = 2; i <= q; i++){
        xltv(query[i].l, query[i].r);
        query[i].ans = cnt;
    }
    sort(query + 1, query + q + 1, cmp);
    for(int i = 1; i <= q; i++){
        cout << query[i].ans << '\n';
    }
}

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

Compilation message (stderr)

poklon.cpp:13:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   13 | const int inf = 1e18;
      |                 ^~~~

• Subtask 1: 140 / 140