Submission #670920

#	Time	Username	Problem	Language	Result	Execution time	Memory
670920		ParsaS	Food Court (JOI21_foodcourt)	C++17	7 / 100	1042 ms	524288 KiB

foodcourt

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 25e4 + 5;
int n, m, q;
vector<pair<int, int> > A[N], B[N];
vector<pair<int, int> > vec[N];
int INX[N];
vector<pair<pair<int, int>, int> > Q[N];
int col[N], ans[N];
int seg[N << 2], lz[N << 2], fen[N];

void updFen(int inx, int val) {
    for (inx; inx <= m; inx += inx & -inx)
        fen[inx] += val;
}
int queryFen(int inx) {
    int res = 0;
    for (inx; inx > 0; inx -= inx & -inx)
        res += fen[inx];
    return res;
}

void shift(int v, int tl, int tr) {
    seg[v] += lz[v];
    if (tl < tr) {
        lz[v << 1] += lz[v];
        lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
}

void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = q) {
    shift(v, tl, tr);
    if (tl > r || tr < l)
        return;
    if (tl >= l && tr <= r) {
        lz[v] += val;
        shift(v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, val, v << 1, tl, mid);
    upd(l, r, val, v << 1 | 1, mid + 1, tr);
    seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = q) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return 1e9 + 10;
    if (tl >= l && tr <= r)
        return seg[v];
    int mid = (tl + tr) >> 1;
    return min(query(l, r, v << 1, tl, mid), query(l, r, v << 1 | 1, mid + 1, tr));
}

void solve() {
    cin >> n >> m >> q;
    int inx = 0;
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int l, r, c, k; cin >> l >> r >> c >> k;

            for (int j = l; j <= r; j++) {
                vec[j].pb(mp(k, c));
            }

        }
        else if (t == 2) {
            int l, r, k; cin >> l >> r >> k;
            int kp = k;
            for (int j = l; j <= r; j++) {
                k = kp;
                if (n <= 2000 && q <= 2000) {
                    while (INX[j] < vec[j].size() && k) {
                        int tmp = min(k, vec[j][INX[j]].fi);
                        k -= tmp;
                        vec[j][INX[j]].fi -= tmp;
                        if (!vec[j][INX[j]].fi)
                            INX[j]++;
                    }
                }
                else {
                    INX[j] = min((int)vec[j].size(), INX[j] + k);
                }
            }

        }
        else {
            int a, b; cin >> a >> b;
			if (n <= 2000 && q <= 2000) {
				int sum = 0, j;
				for (j = 0; j < vec[a].size() && sum < b; j++) {
					sum += vec[a][j].fi;
				}
				if (sum >= b)
					cout << vec[a][--j].se << '\n';
				else
					cout << 0 << '\n';
			}
			else {
				if (vec[a].size() - INX[a] < b) {
					cout << 0 << '\n';
				}
				else {
					cout << vec[a][INX[a] + b - 1].se << '\n';
				}
			}
            continue;
            int sum = 0, j;
            for (j = 0; j < vec[a].size() && sum < b; j++) {
                sum += vec[a][j].fi;
            }
            if (sum >= b)
                cout << vec[a][--j].se << '\n';
            else
                cout << 0 << '\n';
            ans[i] = 0;
            Q[a].pb(mp(mp(inx, i), b));
        }
    }

    /*for (int i = 1; i <= n; i++) {
        for (auto [l, k] : A[i]) {
            upd(l, q, k);
        }
        for (auto tmp : Q[i]) {
            int j = tmp.fi.fi, qi = tmp.fi.se, b = tmp.se;
            int l = -1, r = j + 1;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (query(mid, j) < b)
                    l = mid;
                else
                    r = mid;
            }
            if (query(j + 1, j + 1) >= b) {
                ans[qi] = col[l];
            }
        }
    }
    for (int i = 0; i < q; i++)
        if (ans[i] != -1)
            cout << ans[i] << '\n';*/
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void updFen(ll, ll)':
foodcourt.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (inx; inx <= m; inx += inx & -inx)
      |          ^~~
foodcourt.cpp: In function 'll queryFen(ll)':
foodcourt.cpp:25:10: warning: statement has no effect [-Wunused-value]
   25 |     for (inx; inx > 0; inx -= inx & -inx)
      |          ^~~
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:82:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                     while (INX[j] < vec[j].size() && k) {
      |                            ~~~~~~~^~~~~~~~~~~~~~~
foodcourt.cpp:100:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (j = 0; j < vec[a].size() && sum < b; j++) {
      |                 ~~^~~~~~~~~~~~~~~
foodcourt.cpp:109:32: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
  109 |     if (vec[a].size() - INX[a] < b) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~
foodcourt.cpp:118:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for (j = 0; j < vec[a].size() && sum < b; j++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11