Submission #1124409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124409		ducanh0811	Poklon (COCI17_poklon)	C++20	140 / 140	349 ms	30756 KiB

poklon

#include <bits/stdc++.h>
#define     debug(x)        cout << #x << " = " << x << '\n'
#define     LL              long long
#define     fi              first
#define     se              second
#define     eb              emplace_back
#define     pb              push_back
#define     ALL(x)          x.begin(), x.end()
#define     len(s)          (int)s.size()
#define     MASK(i)         (1ll << (i))
#define     FOR(i,a,b)      for (int i = (a); i <= (b); ++i)
#define     REV(i,a,b)      for (int i = (a); i >= (b); --i)
using namespace std;

int n, m;

#define MAXN 500005

struct event{
    int op, l, r, i, val;
};

int lpos[MAXN];
int rpos[MAXN];
int gpos[MAXN];
int a[MAXN];

vector<event> q;

int bit[MAXN];

void up(int p, int val){
    for (; p <= n; p += p & -p) bit[p] += val;
}

int get(int x){
    int res = 0;
    while (x) res += bit[x], x -= x & -x;
    return res;
}

int get(int u, int v){
    return get(v) - get(u - 1);
}

vector<int> nenso;

int res[MAXN];

void solve(){
    cin >> n >> m;
    FOR(i,1,n){
        cin >> a[i];
        q.pb({0, 0, i, 0, a[i]});
        nenso.eb(a[i]);
    }

    sort(ALL(nenso));
    map<int, int> mp;

    int cur = nenso[0];
    int cnt = 1;
    for (int &x : nenso){
        if (cur != x) cur = x, cnt++;
        mp[cur] = cnt;
    }
    for (event &x : q){
        x.val = mp[x.val];
    }
    FOR(i,1,m){
        int l, r; cin >> l >> r;
        q.pb({1, l, r, i, 0});
    }
    sort(ALL(q), [](const event &A, const event &B){
        if (A.r == B.r) return A.op < B.op;
        return A.r < B.r;
    });

    for (event &x : q){
        if (x.op == 0){
            if (lpos[x.val] == 0){
                lpos[x.val] = x.r;
            } else
            if (lpos[x.val] && rpos[x.val] == 0){
                rpos[x.val] = x.r;
                up(lpos[x.val], 1);
            } else {
                if (gpos[x.val])
                    up(gpos[x.val], 1);
                up(lpos[x.val], -2);
                up(rpos[x.val], 1);
                gpos[x.val] = lpos[x.val];
                swap(lpos[x.val], rpos[x.val]);
                rpos[x.val] = x.r;
            }
        } else {
            res[x.i] = get(x.l, x.r);
        }
    }

    FOR(i,1,m) cout << res[i] << '\n';

}

#define task "BTD"

int32_t main(){
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'int32_t main()':
poklon.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:110:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140