#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
struct meteor{
int l,r,a;
meteor(int ll, int rr, int aa) : l(ll), r(rr), a(aa) {}
meteor() {}
};
int N;
const int maxN = 3e5+10;
int segment[4*maxN], lazy[4*maxN];
void pull(int t){
if(2*t+1 < 4*maxN){
segment[t] = max(segment[2*t], segment[2*t+1]);
}
}
void push(int t){
if(2*t+1 >= 4*maxN) return;
if(lazy[t]){
segment[2*t] += lazy[t];
segment[2*t+1] += lazy[t];
lazy[2*t] += lazy[t];
lazy[2*t+1] += lazy[t];
lazy[t] = 0;
}
}
void modify(int ql, int qr, int c, int l = 0, int r = maxN, int idx = 1){
if(ql >= r || qr <= l) return;
push(idx);
if(ql <= l && qr >= r){
segment[idx] += c;
lazy[idx] += c;
return;
}
modify(ql, qr, c, l, mid, 2*idx);
modify(ql, qr, c, mid, r, 2*idx+1);
pull(idx);
}
int query(int ql, int qr, int l = 0, int r = maxN, int idx = 1){
if(ql >= r || qr <= l) return 0;
push(idx);
if(ql <= l && qr >= r){
return segment[idx];
}
return max(query(ql, qr, l, mid, 2*idx), query(ql, qr, mid, r, 2*idx+1)) ;
}
vector<int> solve(vector<int> landlord, vector<int> owner, vector<int> target, vector<meteor> shower){
int n = (int)landlord.size();
int k = (int)shower.size();
int m = (int)owner.size();
vector<int> returning(N+1, 0);
if(n == 0) return returning;
if(k == 1){
for(int i : landlord){
returning[i] = 1;
}
return returning;
}
F(k/2){
meteor curr = shower[i];
if(curr.l > curr.r){
modify(0, curr.r+1, curr.a);
modify(curr.l, m, curr.a);
}else{
modify(curr.l, curr.r+1, curr.a);
}
}
vector<int> got(N, 0);
vector<int> owning[N];
F(m){
int c = query(i, i+1);
got[owner[i]] += c;
owning[owner[i]].pb(i);
}
vector<int> lland, rland; // left lands and right lands
vector<int> llandlord, rlandlord;
vector<int> ltarget(N, 0);
vector<int> rtarget(N, 0);
// split landlords
for(int i : landlord){
if(got[i] >= target[i]){
for(int j : owning[i]){
lland.pb(j);
}
llandlord.pb(i);
ltarget[i] = target[i];
}else{
for(int j : owning[i]){
rland.pb(j);
}
rlandlord.pb(i);
rtarget[i] = target[i] - got[i];
}
}
sort(all(lland));
sort(all(rland));
vector<int> lowner, rowner;
for(int i : lland){
lowner.pb(owner[i]);
}
for(int i : rland){
rowner.pb(owner[i]);
}
// split queries
vector<meteor> lquery;
vector<meteor> rquery;
F(k){
if(i < k/2){
meteor curr = shower[i];
if(curr.l <= curr.r){
curr.l = (int)get_pos(lland, curr.l);
curr.r++;
curr.r = (int)get_pos(lland, curr.r);
curr.r--;
}else{
curr.r = (int)get_pos(lland, curr.r);
curr.l++;
curr.l = (int)get_pos(lland, curr.l);
curr.l--;
}
lquery.pb(curr);
}else{
meteor curr = shower[i];
if(curr.l <= curr.r){
curr.l = (int)get_pos(rland, curr.l);
curr.r++;
curr.r = (int)get_pos(rland, curr.r);
curr.r--;
}else{
curr.r = (int)get_pos(rland, curr.r);
curr.l++;
curr.l = (int)get_pos(rland, curr.l);
curr.l--;
}
rquery.pb(curr);
}
}
// reset queries
F(k/2){
meteor curr = shower[i];
if(curr.l > curr.r){
modify(1, curr.r+1, -curr.a);
modify(curr.l, m+1, -curr.a);
}else{
modify(curr.l, curr.r+1, -curr.a);
}
}
//solve ...
//solve ...
vector<int> lans = solve(llandlord, lowner,ltarget, lquery);
vector<int> rans = solve(rlandlord, rowner,rtarget, rquery);
for(int i : llandlord){
returning[i] = lans[i];
}
for(int i : rlandlord){
returning[i] = rans[i] + k/2;
}
return returning;
}
signed main(){
int m; // n: landlord, m: pieces of land
cin >> N >> m;
vector<int> owner(m);
vector<int> target(N);
F(m) cin >> owner[i], owner[i]--;
F(N) cin >> target[i];
int k;
cin >> k;
vector<meteor> showers(k);
F(k){
int a,b,c;
cin >> a >> b >> c;
showers[i].l = a-1;
showers[i].r = b-1;
showers[i].a = c;
}
meteor bruh(1, m, 1000000000);
showers.pb(bruh);
vector<int> orig;
F(N) orig.pb(i);
vector<int> res;
res = solve(orig, owner, target, showers);
for(int i : orig){
if(target[i] == 0) {printf("0\n"); continue;}
res[i]--;
if(res[i] == k){
printf("NIE\n");
}else{
printf("%d\n", res[i]+1);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
286 ms |
21124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
917 ms |
16600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
578 ms |
15044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
504 ms |
13268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1193 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1086 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
