Submission #973872

#	Time	Username	Problem	Language	Result	Execution time	Memory
973872		ttttttttttttth	Joker (BOI20_joker)	C++17	0 / 100	1 ms	8792 KiB

Joker

// Author: Ivan Teo
// Created: Wed May 01 17:43:31 2024

#define TASKNAME "coci23c2p5"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

const int N = 2e5 + 5;
int a[N], n, q, bit[N], p[N], ans[N];
ii b[N];

struct Query
{
    int l, r, x, id;
} qr[N];

#define gb(x) ((x) & (-(x)))

void add(int i, int x)
{
    for (; i <= n; i += gb(i)) bit[i] += x;
}

int get(int i)
{
    int res = 0;
    for (; i > 0; i -= gb(i)) res += bit[i];
    return res;
}

int get(int l, int r)
{
    return get(r) - get(l - 1);
}

void upd(int i, int x)
{
    int delta = x - get(i, i);
    add(i, delta);
}

void solve()
{
    cin >> n >> q;
    fore(i, 1, n)
    cin >> a[i], b[i] = {a[i], i};
    sort(b + 1, b + 1 + n);
    fore(i, 1, q) cin >> qr[i].l >> qr[i].r >> qr[i].x, qr[i].id = i;
    sort(qr + 1, qr + 1 + q, [](const Query & a, const Query & b)
    {
        return a.x < b.x;
    });
    int j = 1;
    fill(p + 1, p + 1 + n, 1);
    add(n, 1);
    fore(i, 1, q)
    {
        auto [l, r, x, id] = qr[i];
        while (j <= n && b[j].fi <= x)
        {
            if (p[b[j].se - 1]) add(b[j].se - 1, 1);
            upd(b[j].se, 0);
            p[b[j].se] = 0;
            j++;
        }
        ans[id] = get(l, r);
        if (p[r] && p[r + 1]) ans[id]++;
    }
    fore(i, 1, q) cout << ans[i] << '\n';
}


signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
        freopen(TASKNAME ".inp", "r", stdin),
                freopen(TASKNAME ".out", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
Joker.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(TASKNAME ".inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:99:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |                 freopen(TASKNAME ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29