Submission #1354950

#TimeUsernameProblemLanguageResultExecution timeMemory
1354950retardeFood Court (JOI21_foodcourt)C++20
21 / 100
223 ms24084 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

// max(x + s, m)
// max(max(x + s1, m1) + s2, m2)
// max(max(x + s1 + s2, m1 + s2), m2)
// max(x + s1 + s2, m1 + s2, m2)
// s3 = s1 + s2, m3 = max(m1 + s2, m2)

struct lz {
    int s, m;
    bool operator==(const lz & other) const {
        return (s == other.s && m == other.m);
    }
};
lz sent = {0, (int)-1e18};

// add b to a
lz comb(lz &a, lz &b) {
    if (a == sent) return b;
    if (b == sent) return a;
    lz ans = {a.s + b.s, max(a.m + b.s, b.m)};
    return ans;
}

class st {
    int n;
    vi seg; vector<lz> lazy;

    private:
    void build(int i, int l, int r) {
        if (l > r) return;
        lazy[i] = sent;
        if (l == r) return;
        int mid = (l + r) / 2;
        build(i * 2, l, mid);
        build(i * 2 + 1, mid+1, r);
    }

    void push(int i, int l, int r) {
        if (lazy[i] == sent) return;
        seg[i] = max(seg[i] + lazy[i].s, lazy[i].m);
        if (l == r) {
            lazy[i] = sent;
            return;
        }
        lazy[i * 2] = comb(lazy[i * 2], lazy[i]);
        lazy[i * 2 + 1] = comb(lazy[i * 2 + 1], lazy[i]);
        lazy[i] = sent;
    }

    void update(int i, int l, int r, int ql, int qr, lz tag) {
        push(i, l, r);
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            lazy[i] = comb(lazy[i], tag);
            push(i, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(i * 2, l, mid, ql, qr, tag);
        update(i * 2 + 1, mid + 1, r, ql, qr, tag);
    }

    int query(int i, int l, int r, int qi) {
        push(i, l, r);
        if (l == r) return seg[i];
        int mid = (l + r) / 2;
        if (qi <= mid) return query(i * 2, l, mid, qi);
        else return query(i * 2 + 1, mid + 1, r, qi);
    }

    public:
    st(int qn) {
        n = qn;
        seg.resize(4 * n); lazy.resize(4 * n);
        build(1, 0, n - 1);
    }

    void update(int l, int r, lz tag) {
        update(1, 0, n - 1, l, r, tag);
    }

    int query(int qi) {
        return query(1, 0, n - 1, qi);
    }
};

int n, m, q;

inline void solve() {
    cin >> n >> m >> q;
    st Seg(n);

    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            l--; r--;
            lz tag = {k, (int)-1e18};
            Seg.update(l, r, tag);
            continue;
        }
        if (t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            l--; r--;
            lz tag = {-k, (int)0};
            Seg.update(l, r, tag);
            continue;
        }
        if (t == 3) {
            int a, b;
            cin >> a >> b;
            a--;

            cout << (Seg.query(a) >= b) << '\n';
            continue;
        }
        // assert(false);
    }
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'void setIO(std::string)':
foodcourt.cpp:155:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:156:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...