#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
vector <ll> fen(300002,0);
ll n, m;
ll sum(ll k){
ll s = 0;
while (k >= 1){
s += fen[k];
k -= k&-k;
}
return s;
}
void add(ll k, ll x){
while (k <= m + 2){
fen[k] += x;
k += k&-k;
}
}
int main()
{
cin >> n >> m;
vector <ll> o(m);
for (int i = 0; i < m; i++)
cin >> o[i];
vector <ll> p(n+1);
for (int i = 1; i <= n; i++)
cin >> p[i];
ll k;
cin >> k;
vector <pair <pair <ll,ll>,ll> > q(k);
vector <vector <ll> > stanice(n+1);
for (int i = 0; i < k; i++)
cin >> q[i].first.first >> q[i].first.second >> q[i].second;
for (int i = 0; i < m; i++)
stanice[o[i]].push_back(i+1);
vector <ll> lo(n+1,1);
vector <ll> hi(n+1,k+1);
vector <ll> rjesenja(n+1,-1);
ll rjeseni = 0;
while (rjeseni < n){
vector <pair<ll,ll> > mids(n+1);
for (int i = 1; i <= n; i++)
mids[i].first = (lo[i]+hi[i])/2, mids[i].second = i;
sort(mids.begin(), mids.end());
for (int i = 1; i <= m + 2; i++)
fen[i] = 0;
ll slid = 1;
for (int i = 0; i < k; i++){
ll li = q[i].first.first, de = q[i].first.second, w = q[i].second;
if (li <= de){
add(li, w), add(de + 1, -w);
} else {
add(li,w), add(m + 1, -w);
add(1, w), add(de + 1, -w);
}
while (slid <= n && mids[slid].first == i + 1){
ll pozi = mids[slid].second;
if (rjesenja[pozi] != -1){
slid++;
continue;
}
ll ima = 0;
for (int t = 0; t < stanice[pozi].size(); t++){
ll sta = stanice[pozi][t];
ima += sum(sta);
if (ima >= p[pozi])
break;
}
if (ima >= p[pozi]){
hi[pozi] = i + 1;
} else {
lo[pozi] = i + 2;
}
if (lo[pozi] >= hi[pozi])
rjeseni++, rjesenja[pozi] = lo[pozi];
slid++;
}
}
}
for (int i = 1; i <= n; i++){
if (rjesenja[i] == k + 1)
cout << "NIE" << endl;
else
cout << rjesenja[i] << endl;
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < m; i++)
| ~~^~~
met.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
39 | for (int i = 1; i <= n; i++)
| ~~^~~~
met.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < k; i++)
| ~~^~~
met.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < m; i++)
| ~~^~~
met.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
55 | for (int i = 1; i <= n; i++)
| ~~^~~~
met.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; i <= m + 2; i++)
| ~~^~~~~~~~
met.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < k; i++){
| ~~^~~
met.cpp:69:50: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
69 | while (slid <= n && mids[slid].first == i + 1){
met.cpp:71:36: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
71 | if (rjesenja[pozi] != -1){
met.cpp:76:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int t = 0; t < stanice[pozi].size(); t++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
met.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
93 | for (int i = 1; i <= n; i++){
| ~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2668 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
115 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
261 ms |
6892 KB |
Output is correct |
| 3 |
Correct |
191 ms |
6048 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
172 ms |
5604 KB |
Output is correct |
| 2 |
Correct |
177 ms |
5612 KB |
Output is correct |
| 3 |
Correct |
251 ms |
7008 KB |
Output is correct |
| 4 |
Correct |
90 ms |
5136 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
5356 KB |
Output is correct |
| 2 |
Correct |
229 ms |
6880 KB |
Output is correct |
| 3 |
Correct |
74 ms |
3948 KB |
Output is correct |
| 4 |
Correct |
217 ms |
6372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
126 ms |
4836 KB |
Output is correct |
| 2 |
Correct |
180 ms |
5832 KB |
Output is correct |
| 3 |
Correct |
124 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
263 ms |
7116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1840 ms |
25184 KB |
Output is correct |
| 2 |
Correct |
875 ms |
15336 KB |
Output is correct |
| 3 |
Correct |
369 ms |
10988 KB |
Output is correct |
| 4 |
Correct |
2823 ms |
42380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1680 ms |
23852 KB |
Output is correct |
| 2 |
Correct |
824 ms |
15204 KB |
Output is correct |
| 3 |
Correct |
368 ms |
10988 KB |
Output is correct |
| 4 |
Correct |
3092 ms |
45732 KB |
Output is correct |
