QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#883563#7641. Range SetsDeltaCRTL 0ms0kbC++142.5kb2025-02-05 17:01:062025-02-05 17:01:07

Judging History

This is the latest submission verdict.

  • [2025-02-05 17:01:07]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-05 17:01:06]
  • Submitted

answer

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2e5;
const int X = 1e5;
const int Q = 1e5;

int m;
map<int, int> mp;
vector<int> val;

struct Opt
{
    char op;
    int l, r, x, k;
} opt[Q + 5];

struct BIT
{
private:
    int tree[N + 5];
    int lowbit(int x)
    {
        return x & -x;
    }

    void update(int x, int d)
    {
        while (x <= m)
        {
            tree[x] += d;
            x += lowbit(x);
        }
    }

public:
    void update(int l, int r, int d)
    {
        update(l, d);
        update(r + 1, -d);
    }

    int query(int x)
    {
        int res = 0;
        while (x)
        {
            res += tree[x];
            x -= lowbit(x);
        }

        return res;
    }
} ans;

struct Chtholly
{
private:
    map<int, bool> ch;
    void split(int x) // 将 x 所在段 [l, r] 分为 [l, x - 1] 与 [x, r] 两部分
    {
        ch[x] = prev(ch.upper_bound(x))->second;
    }

public:
    void init(int n)
    {
        ch[1] = ch[n + 1] = 0;
    }

    void update(int l, int r, bool x) // 将 [l, r] 内的值修改为 x
    {
        split(l), split(r + 1);
        for (auto i = ch.find(l); i != ch.find(r + 1); ++i)
            if (i->second != x)
                ans.update(mp[i->first], mp[next(i)->first - 1], x - i->second);
        for (auto i = next(next(ch.find(l))); i != ch.find(r + 1); ++i)
            ch.erase(prev(i));
        ch[l] = x;
    }
} have[X + 5];

void init()
{
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for (int i = 0; i < val.size(); ++i) mp[val[i]] = i + 1;
    m = val.size();
}

int main()
{
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= q; ++i)
    {
        have[i].init(n);
        cin >> opt[i].op;
        if (opt[i].op == '+' || opt[i].op == '-')
        {
            cin >> opt[i].l >> opt[i].r >> opt[i].x;
            val.push_back(opt[i].l);
            val.push_back(opt[i].r);
        }
        else
        {
            cin >> opt[i].k;
            val.push_back(opt[i].k);
        }
    }

    init();
    for (int i = 1; i <= q; ++i)
    {
        if (opt[i].op == '+') have[opt[i].x].update(opt[i].l, opt[i].r, true);
        else if (opt[i].op == '-') have[opt[i].x].update(opt[i].l, opt[i].r, false);
        else cout << ans.query(mp[opt[i].k]) << endl;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

736 10
? 1

output:


result: