POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met

N, M, K ≤ 3e5
MAXP, MAXA ≤ 1e9
TL: 10000 ms
ML: 64 MB

O( ( N + M ) * lg K * lg M ) / O( N + M )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 3e5;
const int MAXM = ( int ) 3e5;
const int MAXK = ( int ) 3e5;

int N, M;
int O[ MAXM ]; // owner of field
vector< int > rO[ MAXN ]; // owner to field
int P[ MAXN ]; // goal
int K;
int L[ MAXK ], R[ MAXK ], W[ MAXK ]; // [ L, R ], might be cirucular

int ans[ MAXN ];

struct Fenwick_Tree{
long long sum[ MAXM + 10 ]; // sum[ 1 ] = A[ 0 ], sum[ 1 ] + sum[ 2 ] = A[ 1 ]
void add( int ql, int qr, int v ){ // [ ql, qr ) - 0 base
++ql, ++qr;
for( int i = ql; i < M + 5; i += i & -i ){
sum[ i ] += v;
}
for( int i = qr; i < M + 5; i += i & -i ){
sum[ i ] -= v;
}
}
long long gs( int x ){ // A[ x ] = S[ 1, x + 1 ]
++x;
long long res = 0LL;
for( int i = x; i; i -= i & -i ){
res += sum[ i ];
}
return res;
}
} ftree;

void parallel_bs( int lb, int rb, vector< int > &nation ){
if( lb + 1 == rb ){
for( int i = 0; i < nation.size(); ++i ){
int owner = nation[ i ];
for( int j = 0; j < rO[ owner ].size(); ++j ){
if( L[ lb ] <= R[ lb ] ){
if( L[ lb ] <= rO[ owner ][ j ] and rO[ owner ][ j ] <= R[ lb ] ){
P[ owner ] -= W[ lb ];
}
} else{
if( rO[ owner ][ j ] <= R[ lb ] or L[ lb ] <= rO[ owner ][ j ] ){
P[ owner ] -= W[ lb ];
}
}
if( P[ owner ] <= 0 ) break;
}
if( P[ owner ] <= 0 ){
ans[ owner ] = rb;
} else{
ans[ owner ] = -1;
}
}
return;
}
int mid = lb + rb >> 1;
{ // update contribution of [ lb, mid ) to ftree
for( int i = lb; i < mid; ++i ){
if( L[ i ] <= R[ i ] ){
ftree.add( L[ i ], R[ i ] + 1, W[ i ] );
} else{
ftree.add( 0, R[ i ] + 1, W[ i ] );
ftree.add( L[ i ], M, W[ i ] );
}
}
}
vector< int > ll, rr;
{ // split nation
static long long taken[ MAXN ];
for( int i = 0; i < nation.size(); ++i ){
int owner = nation[ i ];
taken[ owner ] = 0LL;
for( int j = 0; j < rO[ owner ].size(); ++j ){
int field = rO[ owner ][ j ];
taken[ owner ] += ftree.gs( field );
if( taken[ owner ] >= P[ owner ] ) break;
}
if( taken[ owner ] >= P[ owner ] ){
ll.push_back( owner );
} else{
P[ owner ] -= taken[ owner ]; // cancel contribution of [ lb, mid ) from P
rr.push_back( owner );
}
}
}
{ // cancel contribution of [ lb, mid ) from ftree
for( int i = lb; i < mid; ++i ){
if( L[ i ] <= R[ i ] ){
ftree.add( L[ i ], R[ i ] + 1, - W[ i ] );
} else{
ftree.add( 0, R[ i ] + 1, - W[ i ] );
ftree.add( L[ i ], M, - W[ i ] );
}
}
}
parallel_bs( lb, mid, ll );
parallel_bs( mid, rb, rr );
}

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> M;
for( int i = 0; i < M; ++i ){
cin >> O[ i ]; --O[ i ];
rO[ O[ i ] ].push_back( i );
}
for( int i = 0; i < N; ++i ){
cin >> P[ i ];
}
cin >> K;
for( int i = 0; i < K; ++i ){
cin >> L[ i ] >> R[ i ] >> W[ i ];
--L[ i ], --R[ i ];
}
}
{
vector< int > nation( N );
for( int i = 0; i < N; ++i ){
nation[ i ] = i;
}
parallel_bs( 0, K, nation );
}
{
for( int i = 0; i < N; ++i ){
if( ans[ i ] == -1 ){
cout << "NIE\n";
} else{
cout << ans[ i ] << "\n";
}
}
}
return 0;
}
```