제출 #1188749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188749		_dtq_	Poklon (COCI17_poklon)	C++17	0 / 140	931 ms	44168 KiB

poklon

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (long long)(x.size())
using namespace std;

const ll N = 5e5 + 9;

ll n, i, q, l, r, a[N], ans[N], dem[N];

vector<ll>vec;

void calc( ll l, ll r )
{
    for( int w = l; w <= r; w ++ ) dem[a[w]] ++;

    for( int w = l; w <= r; w ++ )
    {
        ans[i] += (dem[a[w]] == 2);

        dem[a[w]] = 0;
    }
}

struct abc{
   ll l, r, id;
};

vector<abc>save[N];

bool cmp( abc x, abc y )
{
    return x.r < y.r;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;

    for( i = 1; i <= n; i ++ )
        cin >> a[i], vec.pb(a[i]);

        sort(all(vec));

        for( i = 1; i <= n; i ++ ) a[i] = lower_bound(all(vec), a[i]) - vec.begin();

    ll c = sqrt(n);

    if(c * c != n) c ++;

    for( i = 1; i <= q; i ++ )
    {
        cin >> l >> r;

        if(r - l + 1 <= c)
        {
            calc(l, r);

            continue;
        }

        ll block = l / c + (l % c != 0);

        save[block].pb({l, r, i});
    }

    for( i = 1; i <= c + 2; i ++ )
        sort(all(save[i]), cmp);

    for( i = 1; i <= c + 2; i ++ )
    {
        if(sz(save[i]) == 0) continue;

        ll x = (i - 1) * c + 1, y = min(n, i * c);

        ll cnt = 0;

        ll vt = y + 1;

        for(auto k : save[i])
        {
            ll l = k.l, r = k.r;

            for( int w = l; w <= y; w ++ )
            {
                dem[a[w]] ++;

                cnt += (dem[a[w]] == 2);

                cnt -= (dem[a[w]] == 3);
            }

            while(vt <= r)
            {
                dem[a[vt]] ++;

                cnt += (dem[a[vt]] == 2);

                cnt -= (dem[a[vt]] == 3);

                vt ++;
            }

            ans[k.id] = cnt;

            for( int w = l; w <= y; w ++ )
            {
                dem[a[w]] --;

                cnt += (dem[a[w]] == 2);

                cnt -= (dem[a[w]] == 1);
            }
        }
    }

    for( i = 1; i <= q; i ++ )
        cout << ans[i] << "\n";
    return 0;
}
/*
*/

• Subtask 1: 0 / 140