| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1153001 | TVSown | Meteors (POI11_met) | C++20 | 0 ms | 0 KiB |
///*** Sown_Vipro ***///
/// ->TEAM SELECTION TEST<- ///
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
//#define int long long
const string NAME = "sown";
const int N = 3e5 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
void maxi(int &x, int y){ if(x < y) x = y; }
void mini(int &x, int y){ if(x > y) x = y; };
void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); };
int n, m, k;
int p[N], o[N], l[N], r[N], rs[4 * N];
long long st[4 * N];
vector<int> adj[N];
struct query{
int l, r, a;
} Q[N];
void down(int id){
if(rs[id]){
st[2 * id] = st[2 * id + 1] = 0;
rs[2 * id] = rs[2 * id + 1] = 1;
rs[id] = 0;
}
if(st[id]){
// cout << st[id] << "\n";
st[2 * id] += st[id];
st[2 * id + 1] += st[id];
st[id] = 0;
}
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u) return;
if(u <= l && r <= v){
st[id] += x;
// cout << l << " " << r << " " << x << "\n";
return;
}
down(id);
int m = (l + r) / 2;
update(2 * id, l, m, u, v, x);
update(2 * id + 1, m + 1, r, u, v, x);
}
long long get(int id, int l, int r, int i){
if(l > i || r < i) return 0;
if(l == r){
// cout << "test: " << l << " " << r << " " << st[id] << "\n";
return st[id];
}
down(id);
// cout << l << " " << r << "\n";
int m = (l + r) / 2;
return get(2 * id, l, m, i) + get(2 * id + 1, m + 1, r, i);
}
int check(int o){
long long s = 0;
for(int i : adj[o]){
s += get(1, 1, m, i);
s = min(s, p[o] + 1);
}
return s >= p[o];
}
void solve(){
cin >> n >> m;
FOR(i, 1, m){
cin >> o[i];
adj[o[i]].pb(i);
}
FOR(i, 1, n) cin >> p[i];
cin >> k;
FOR(i, 1, k){
cin >> Q[i].l >> Q[i].r >> Q[i].a;
}
FOR(i, 1, n){
l[i] = 0, r[i] = k;
}
int c = 1, time = 0;
vector<vector<int> > q = vector<vector<int> > (k + 5, vector<int> (0));
while(c){
++time;
// if(time == 4) break;
c = 0;
st[1] = 0; rs[1] = 1;
FOR(o, 1, n){
if(l[o] > r[o]) continue;
c = 1;
// cout << (r[o] - l[o]) << "\n";
q[(r[o] + l[o]) / 2].pb(o);
}
// cout << c << "\n";
FOR(i, 0, k){
if(i){
if(Q[i].l <= Q[i].r){
update(1, 1, m, Q[i].l, Q[i].r, Q[i].a);
}else{
update(1, 1, m, Q[i].l, m, Q[i].a);
update(1, 1, m, 1, Q[i].r, Q[i].a);
}
}
for(int o : q[i]){
// cout << i << " " << o << " " << l[o] << " " << r[o] << "\n";
if(check(o)) r[o] = i - 1;
else l[o] = i + 1;
// cout << o << " " << l[o] << " " << r[o] << "\n";
}
q[i].clear();
}
}
FOR(i, 1, n){
// cout << l[i] << " " << r[i] << "\n";
if(l[i] == k + 1) cout << "NIE\n";
else cout << l[i] << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen((NAME + ".inp").c_str(), "r")){
freopen((NAME + ".inp").c_str(), "r", stdin);
// freopen((NAME + ".out").c_str(), "w", stdout);
}
int t = 1;
// cin >> t;
while(t--){
solve();
}
}