oj.uz

Submission #201670

# Submission time Handle Problem Language Result Execution time Memory
201670 2020-02-11T16:49:50 Z SamAnd Poklon (COCI17_poklon) C++17
140 / 140
 1537 ms 18416 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int s;
struct ban
{
    int i;
    int l, r;
};
bool operator<(const ban& a, const ban& b)
{
    if ((a.l / s) < (b.l / s))
        return true;
    if ((a.l / s) > (b.l / s))
        return false;
    if ((a.l / s) % 2)
        return a.r < b.r;
    return a.r > b.r;
}

int n, m;
int a[N];
ban b[N];

int yans;
int q[N];
void ave(int x)
{
    if (q[x] == 2)
        --yans;
    ++q[x];
    if (q[x] == 2)
        ++yans;
}
void han(int x)
{
    if (q[x] == 2)
        --yans;
    --q[x];
    if (q[x] == 2)
        ++yans;
}

int ans[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int z = 0;
    vector<int> v;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i)
        v.push_back(a[i]);
    sort(v.begin(), v.end());
    for (int i = 0; i < n; ++i)
    {
        if (!i || v[i] != v[i - 1])
            mp[v[i]] = ++z;
    }
    for (int i = 1; i <= n; ++i)
        a[i] = mp[a[i]];
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &b[i].l, &b[i].r);
        b[i].i = i;
    }
    s = sqrt(n);
    sort(b + 1, b + m + 1);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i)
    {
        int ll = b[i].l, rr = b[i].r;
        while (r < rr)
        {
            ++r;
            ave(a[r]);
        }
        while (l > ll)
        {
            --l;
            ave(a[l]);
        }
        while (r > rr)
        {
            han(a[r]);
            --r;
        }
        while (l < ll)
        {
            han(a[l]);
            ++l;
        }
        ans[b[i].i] = yans;
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
poklon.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
poklon.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &b[i].l, &b[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 10 ms 504 KB Output is correct
5 Correct 179 ms 4464 KB Output is correct
6 Correct 184 ms 4464 KB Output is correct
7 Correct 471 ms 8848 KB Output is correct
8 Correct 795 ms 13120 KB Output is correct
9 Correct 1125 ms 15804 KB Output is correct
10 Correct 1537 ms 18416 KB Output is correct