oj.uz

답안 #955330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955330 2024-03-30T06:45:26 Z vjudge1 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 378 ms 46656 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e17) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

#define int ll

struct segTree
{
    struct Node
    {
        int mx, op;
    };
    vector<Node> tree;
    int sz = 0;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz);
    }

    void upd(int v, int val)
    {
        tree[v].op += val;
        tree[v].mx += val;
    }

    void push(int v, int lv, int rv)
    {
        if (rv - lv == 1 or tree[v].op == 0)
            return;
        upd(v * 2 + 1, tree[v].op);
        upd(v * 2 + 2, tree[v].op);
        tree[v].op = 0;
    }

    void updSeg(int l, int r, int val, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
        {
            upd(v, val);
            return;
        }
        if (rv <= l or r <= lv)
            return;
        int m = (lv + rv) >> 1;
        updSeg(l, r, val, v * 2 + 1, lv, m);
        updSeg(l, r, val, v * 2 + 2, m, rv);
        tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
    }

    void updSeg(int l, int r, int val)
    {
        updSeg(l, r, val, 0, 0, sz);
    }

    int getPos(int pos, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
            return tree[v].mx;
        int m = (lv + rv) >> 1;
        if (pos < m)
            return getPos(pos, v * 2 + 1, lv, m);
        return getPos(pos, v * 2 + 2, m, rv);
    }

    int getPos(int pos)
    {
        return getPos(pos, 0, 0, sz);
    }

    int getGoodPos(int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
            return lv;
        int m = (lv + rv) >> 1;
        if (tree[v * 2 + 1].mx >= 0)
            return getGoodPos(v * 2 + 1, lv, m);
        return getGoodPos(v * 2 + 2, m, rv);
    }

    int getGoodPos()
    {
        return getGoodPos(0, 0, sz);
    }
};

struct segTreeBF
{
    struct Node
    {
        int mx, op;
    };
    vector<Node> tree;
    int sz = 0;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz);
    }

    void upd(int v, int val)
    {
        tree[v].op += val;
        tree[v].mx += val;
        tree[v].mx = max(tree[v].mx, 0LL);
    }

    void push(int v, int lv, int rv)
    {
        if (rv - lv == 1 or tree[v].op == 0)
            return;
        upd(v * 2 + 1, tree[v].op);
        upd(v * 2 + 2, tree[v].op);
        tree[v].op = 0;
    }

    void updSeg(int l, int r, int val, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
        {
            upd(v, val);
            return;
        }
        if (rv <= l or r <= lv)
            return;
        int m = (lv + rv) >> 1;
        updSeg(l, r, val, v * 2 + 1, lv, m);
        updSeg(l, r, val, v * 2 + 2, m, rv);
        tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
    }

    void updSeg(int l, int r, int val)
    {
        updSeg(l, r, val, 0, 0, sz);
    }

    int getPos(int pos, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
            return tree[v].mx;
        int m = (lv + rv) >> 1;
        if (pos < m)
            return getPos(pos, v * 2 + 1, lv, m);
        return getPos(pos, v * 2 + 2, m, rv);
    }

    int getPos(int pos)
    {
        return getPos(pos, 0, 0, sz);
    }

    int getGoodPos(int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (tree[v].mx < 0)
            return -1;
        if (rv - lv == 1)
            return lv;
        int m = (lv + rv) >> 1;
        if (tree[v * 2 + 1].mx >= 0)
            return getGoodPos(v * 2 + 1, lv, m);
        return getGoodPos(v * 2 + 2, m, rv);
    }

    int getGoodPos()
    {
        return getGoodPos(0, 0, sz);
    }
};

struct test
{
    void solve(int testcase)
    {
        boost();
        int n, m, q;
        cin >> n >> m >> q;
        int cntA = 0;
        vector<vector<pair<pii, int>>> ops(n);

        vector<pair<pii, pii>> updates;
        segTreeBF bf1, bf2;
        vector<int> ans;
        bf1.init(n);
        bf2.init(n);
        for (int i = 0; i < q; ++i)
        {
            int tp;
            cin >> tp;
            if (tp == 1)
            {
                int l, r, c, k;
                cin >> l >> r >> c >> k;
                --l;
                updates.pb({{l, r}, {c, k}});
                bf1.updSeg(l, r, k);
                bf2.updSeg(l, r, k);
            }
            else if (tp == 2)
            {
                int l, r, k;
                cin >> l >> r >> k;
                --l;
                bf2.updSeg(l, r, -k);
            }
            else
            {
                int p, val;
                cin >> p >> val;
                --p;
                int cntLeave = bf1.getPos(p) - bf2.getPos(p);
                ans.pb(0);
                if (bf2.getPos(p) >= val)
                {
                    ops[p].pb({{cntLeave, val}, cntA});
                }
                cntA++;
            }
        }
        for (int i = 0; i < n; ++i)
            ops[i].pb({{INF, INF}, BIG});
        segTree res;
        res.init(n + 1);
        for (int i = 0; i < n; ++i)
        {
            reverse(all(ops[i]));
            pii val = ops[i].back().f;
            res.updSeg(i, i + 1, -val.s - val.f);
        }

        for (auto [seg, vals] : updates)
        {
            res.updSeg(seg.f, seg.s, vals.s);
            int p = res.getGoodPos();
            while (p < n)
            {
                ans[ops[p].back().s] = vals.f;
                ops[p].pop_back();
                pii val = ops[p].back().f;
                res.updSeg(p, p + 1, -val.s - val.f - res.getPos(p));
                p = res.getGoodPos();
            }
        }

        for (auto el : ans)
            cout << el << '\n';
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message

foodcourt.cpp:349:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  349 | main()
      | ^~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 12220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 378 ms 46656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 13268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -