oj.uz

Submission #818906

# Submission time Handle Problem Language Result Execution time Memory
818906 2023-08-10T07:15:43 Z vjudge1 Poklon (COCI17_poklon) C++17
98 / 140
 760 ms 122516 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

using namespace std;

const int N = 1e6+7;
const int oo = 1e9+7;

int n, q;
ll s[N], a[N], pre[N], res[N],idx[N];
vector<pair<ll, int>> v[N];
vector<int>b;

void update(int id, int l, int r, int x, int val)
{
    if (l > x || r < x)
        return;
    if (l == r)
    {
        s[id] += val;
        return;
    }

    int mid = (l + r) /2;
    update(id * 2, l, mid, x, val);
    update(id * 2 + 1, mid + 1, r, x, val);
    s[id] = s[id * 2] + s[id * 2 + 1];
}

ll get(int id, int l, int r, int x, int y)
{
    if (l > y || r < x)
        return 0;
    if (x <= l && r <= y)
        return s[id];

    int mid = (l + r) / 2;
    return get(id * 2, l, mid, x, y) + get(id * 2 + 1, mid + 1, r, x, y);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen(".INP", "r", stdin);
//    freopen(".OUT", "w", stdout);
    cin>> n>> q;
    for (int i = 1; i <= n; i++)
    {
        cin>> a[i];
       b.pb(a[i]);
    }
    sort(b.begin(),b.end());
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin>> l>> r;
        v[r].pb({l, i});
    }
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(all(b),a[i]) - b.begin() + 1;
        idx[i] = pre[p];
        pre[p] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        int x = idx[i];
        int y = idx[x];
        int z = idx[y];
        if (x > 0)
            update(1, 1, n, x, 1);
        if (y > 0)
            update(1, 1, n, y, -2);
        if(z) update(1,1,n,z,1);
        for (auto l:v[i])
            res[l.se] = get(1, 1, n, l.fi, i);
    }
    for (int i = 1; i <= q; i++)
        cout<< res[i]<< '\n';
    return 0;
}

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23780 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 16 ms 24256 KB Output is correct
5 Correct 143 ms 31596 KB Output is correct
6 Correct 119 ms 31776 KB Output is correct
7 Correct 303 ms 40500 KB Output is correct
8 Runtime error 415 ms 100596 KB Execution killed with signal 11
9 Runtime error 542 ms 111592 KB Execution killed with signal 11
10 Runtime error 760 ms 122516 KB Execution killed with signal 11