#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);
const int MAXN = 300005;
int n, m, a, q;
vector<int> v[MAXN];
pair< pii, int > w[MAXN];
ll loga[MAXN];
void update(int x, int y) {
x++;
for (; x <= 300000; x += x & -x) loga[x] += y;
}
ll query(int x) {
x++;
ll out = 0;
for (; x > 0; x -= x & -x) out += loga[x];
return out;
}
vector< pair<pii, int> > gdje[MAXN];
vector< pair<pii, int> > slj[MAXN];
int sol[MAXN];
int treba[MAXN];
int main () {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a;
v[a-1].push_back(i);
}
for (int i = 0; i < n; i++) cin >> treba[i];
cin >> q;
for (int i = 0; i < q; i++) {
cin >> w[i].X.X >> w[i].X.Y >> w[i].Y;
w[i].X.X --;
w[i].X.Y --;
}
/*for (int i = 0; i < q; i++) {
if (w[i].X.X <= w[i].X.Y) {
update(w[i].X.X, w[i].Y);
update(w[i].X.Y+1, -w[i].Y);
}
else {
update(w[i].X.X, w[i].Y);
update(0, w[i].Y);
update(w[i].X.Y+1, -w[i].Y);
}
}*/
int kol = n;
for (int i = 0; i < n; i++) {
gdje[(q-1)/2].push_back({{0, q-1}, i});
}
memset(sol, -1, sizeof sol);
int br = 0;
while (kol > 0) {
for (int i = 0; i < q; i++) {
if (w[i].X.X <= w[i].X.Y) {
update(w[i].X.X, w[i].Y);
update(w[i].X.Y+1, -w[i].Y);
}
else {
update(w[i].X.X, w[i].Y);
update(0, w[i].Y);
update(w[i].X.Y+1, -w[i].Y);
}
/*cout << "QUERY" << endl;
for (int j = 0; j < m; j++) cout << query(j) << " ";
cout << endl; */
for (int j = 0; j < gdje[i].size(); j++) {
unsigned long long zbr = 0;
for (int k = 0; k < v[gdje[i][j].Y].size(); k++) {
//cout << "dodaj poziciju " << v[gdje[i][j].Y][k] << endl;
zbr += query(v[gdje[i][j].Y][k]);
if (zbr >= treba[gdje[i][j].Y]) break;
}
//cout << gdje[i][j].X.X << " do " << gdje[i][j].X.Y << ": " << gdje[i][j].Y << " " << zbr << endl;
//system("pause");
if (gdje[i][j].X.X == gdje[i][j].X.Y) {
if (zbr >= treba[gdje[i][j].Y]) sol[gdje[i][j].Y] = i+1;
else sol[gdje[i][j].Y] = -1;
kol--;
}
else {
if (zbr < treba[gdje[i][j].Y]) slj[(i+1+gdje[i][j].X.Y)/2].push_back({{i+1, gdje[i][j].X.Y}, gdje[i][j].Y});
else {
slj[(gdje[i][j].X.X+i)/2].push_back({{gdje[i][j].X.X, i}, gdje[i][j].Y});
}
}
}
}
for (int i = 0; i < q; i++) {
gdje[i].clear();
gdje[i].shrink_to_fit();
gdje[i] = slj[i];
slj[i].clear();
slj[i].shrink_to_fit();
}
memset(loga, 0, sizeof loga);
br++;
}
for (int i = 0; i < n; i++) {
if (sol[i] == -1) cout << "NIE\n";
else cout << sol[i] << "\n";
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int j = 0; j < gdje[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
met.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int k = 0; k < v[gdje[i][j].Y].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:93:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
93 | if (zbr >= treba[gdje[i][j].Y]) break;
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
met.cpp:100:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
100 | if (zbr >= treba[gdje[i][j].Y]) sol[gdje[i][j].Y] = i+1;
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
met.cpp:106:14: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
106 | if (zbr < treba[gdje[i][j].Y]) slj[(i+1+gdje[i][j].X.Y)/2].push_back({{i+1, gdje[i][j].X.Y}, gdje[i][j].Y});
| ~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
25068 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25068 KB |
Output is correct |
| 3 |
Correct |
22 ms |
25100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
25068 KB |
Output is correct |
| 2 |
Correct |
21 ms |
25068 KB |
Output is correct |
| 3 |
Correct |
20 ms |
25068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
26172 KB |
Output is correct |
| 2 |
Correct |
224 ms |
27352 KB |
Output is correct |
| 3 |
Correct |
196 ms |
27028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
26836 KB |
Output is correct |
| 2 |
Correct |
205 ms |
26688 KB |
Output is correct |
| 3 |
Correct |
225 ms |
27556 KB |
Output is correct |
| 4 |
Correct |
67 ms |
26300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
26440 KB |
Output is correct |
| 2 |
Correct |
227 ms |
27700 KB |
Output is correct |
| 3 |
Correct |
168 ms |
25708 KB |
Output is correct |
| 4 |
Correct |
190 ms |
27296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
25836 KB |
Output is correct |
| 2 |
Correct |
203 ms |
26684 KB |
Output is correct |
| 3 |
Correct |
153 ms |
26092 KB |
Output is correct |
| 4 |
Correct |
237 ms |
27968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1518 ms |
36948 KB |
Output is correct |
| 2 |
Correct |
935 ms |
29808 KB |
Output is correct |
| 3 |
Correct |
908 ms |
28140 KB |
Output is correct |
| 4 |
Correct |
2419 ms |
45608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1513 ms |
36488 KB |
Output is correct |
| 2 |
Correct |
909 ms |
29804 KB |
Output is correct |
| 3 |
Correct |
715 ms |
27372 KB |
Output is correct |
| 4 |
Correct |
2600 ms |
48316 KB |
Output is correct |
