#include <bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<ll, ll>;
struct ura1 {
int n;
vll V;
ura1(int N) : n(N), V(N, 0) {}
void update(int p, int v) {
///update pe pozitie
V[p] = v;
}
int query(int p) {
/// va returna suma maxima pt (i...p)
int re = V[p], s = V[p];
for(int i = p - 1; i >= 0; --i) {
s += V[i];
re = max(re, s);
}
return re;
}
};
struct ura2 {
ll n, sumtot = 0;
vll V;
ura2(int N) : n(N), V(N) {}
void update(int p, int v) {
///update pe pozitie
sumtot -= V[p];
V[p] = v;
sumtot += V[p];
}
int sum() {
return sumtot;
}
int query(int nr) {
/// va returna pozitia celul a al nr-lea element
ll s = 0;
for(int i = 0; i < n; ++i) {
s += V[i];
if(s >= nr) return i;
}
assert(0);
}
};
signed main() {
int n, m, q;
cin >> n >> m >> q;
vi V1, V2, C2;
vector<ii> UpV1, UpV2; /// toggle-uri pe timp
struct query {
int poz, id, ultV1;
};
vector<vector<query> > Q(n);
int nr3 = 0;
for (int i = 0; i < q; ++i) {
int tip;
cin >> tip;
if (tip == 1) {
int l, r, c, k;
cin >> l >> r >> c >> k;
--l; --r;
UpV1.push_back({l, V1.size()});
UpV1.push_back({r + 1, V1.size()});
UpV2.push_back({l, V2.size()});
UpV2.push_back({r + 1, V2.size()});
V1.push_back(k);
V2.push_back(k);
C2.push_back(c);
} else if (tip == 2) {
int l, r, k;
cin >> l >> r >> k;
--l; --r;
UpV1.push_back({l, V1.size()});
UpV1.push_back({r + 1, V1.size()});
V1.push_back(-k);
} else {
int a, b;
cin >> a >> b;
--a;
Q[a].push_back({b, nr3, int(V1.size()) - 1});
++nr3;
}
}
sort(UpV1.begin(), UpV1.end());
sort(UpV2.begin(), UpV2.end());
int p1 = 0, p2 = 0;
vi Re(nr3);
ura1 Sol1(V1.size());
vi on1(V1.size(), 0);
ura2 Sol2(V2.size());
vi on2(V2.size(), 0);
for(int i = 0; i < n; ++i) {
while(p1 < UpV1.size() && UpV1[p1].first <= i) {
//toggle it
int v = UpV1[p1].second;
if(!on1[v]) Sol1.update(v, V1[v]);
else Sol1.update(v, 0);
on1[v] ^= 1;
++p1;
}
while(p2 < UpV2.size() && UpV2[p2].first <= i) {
//toggle it
int v = UpV2[p2].second;
if(!on2[v]) Sol2.update(v, V2[v]);
else Sol2.update(v, 0);
on2[v] ^= 1;
++p2;
}
for(auto q : Q[i]) {
ll nrsuf = Sol1.query(q.ultV1), nrtot = Sol2.sum();
ll b = q.poz + nrtot - nrsuf;
if(b > nrtot) {
Re[q.id] = 0;
} else {
Re[q.id] = C2[Sol2.query(b)];
}
}
}
for(auto it : Re) cout << it << "\n";
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:107:18: 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]
107 | while(p1 < UpV1.size() && UpV1[p1].first <= i) {
| ~~~^~~~~~~~~~~~~
foodcourt.cpp:116:18: 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]
116 | while(p2 < UpV2.size() && UpV2[p2].first <= i) {
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
7792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1057 ms |
30004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
759 ms |
7848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
