#include<bits/stdc++.h>
using namespace std ;
const int MX = 3e5 + 5 ;
const long long INF = 1e18 + 5 ;
struct query
{
int l = 0 , r = 0 ;
long long val = 0 ;
};
struct BIT
{
int n ;
vector<long long> bit ;
void init(int _n)
{
n = _n ;
bit = vector<long long>(n+5,0) ;
}
int low_bit(int idx)
{
return idx&(-idx) ;
}
void add(int idx , long long val)
{
for(; idx <= n ; idx += low_bit(idx))
{
bit[idx] += val ;
}
}
void update(int l , int r , long long val)
{
add(r + 1 , -val) , add(l , val) ;
if(l>r) add(1,val) , add(n+1,-val) ;
}
long long query(int idx)
{
long long ret = 0 ;
for(; idx > 0 ; idx -= low_bit(idx))
{
ret += bit[idx] ;
}
return ret ;
}
} B ;
int n , m , k , o[MX] , ans[MX] ;
long long p[MX] ;
vector<int> owner[MX] ;
vector<query> q ;
void palbs(int low , int high , vector<int> &vals)
{
if(low==high)
{
for(int &i : vals)
{
ans[i] = low ;
}
return ;
}
int mid = (low+high)>>1 ;
for(int i = low ; i <= mid ; ++i)
{
B.update(q[i].l,q[i].r,q[i].val) ;
}
vector<int> ok , not_ok ;
for(int c : vals)
{
long long sum = 0 ;
for(int land : owner[c])
{
sum += B.query(land) ;
}
if(sum>=p[c]) ok.push_back(c) ;
else
{
p[c] -= sum ;
not_ok.push_back(c) ;
}
}
for(int i = low ; i <= mid ; ++i)
{
B.update(q[i].l,q[i].r,-q[i].val) ;
}
palbs(low,mid,ok) ;
palbs(mid+1,high,not_ok) ;
}
int main()
{
vector<int> v ;
scanf("%d%d",&n,&m) ;
B.init(m+2) ;
for(int i = 1 ; i <= m ; ++i)
{
scanf("%d",&o[i]) ;
owner[o[i]].push_back(i) ;
}
for(int i = 1 ; i <= n ; ++i)
{
scanf("%lld",&p[i]) ;
ans[i] = -1 ;
v.push_back(i) ;
}
scanf("%d",&k) ;
for(int i = 1 ; i <= k ; ++i)
{
int l , r ;
long long a ;
scanf("%d%d%lld",&l,&r,&a) ;
q.push_back({l,r,a}) ;
}
q.push_back({1,m,INF}) ;
palbs(0,k,v) ;
for(int i = 1 ; i <= n ; ++i)
{
if(ans[i]!=k) printf("%d\n",ans[i]+1) ;
else puts("NIE") ;
}
return 0 ;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d%d",&n,&m) ;
| ~~~~~^~~~~~~~~~~~~~
met.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d",&o[i]) ;
| ~~~~~^~~~~~~~~~~~
met.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%lld",&p[i]) ;
| ~~~~~^~~~~~~~~~~~~~
met.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d",&k) ;
| ~~~~~^~~~~~~~~
met.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d%d%lld",&l,&r,&a) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7448 KB |
Output is correct |
3 |
Correct |
5 ms |
7368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7364 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
5 ms |
7364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
10316 KB |
Output is correct |
2 |
Correct |
95 ms |
12552 KB |
Output is correct |
3 |
Correct |
79 ms |
10764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
10740 KB |
Output is correct |
2 |
Correct |
88 ms |
10760 KB |
Output is correct |
3 |
Correct |
95 ms |
11992 KB |
Output is correct |
4 |
Correct |
30 ms |
9760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
10308 KB |
Output is correct |
2 |
Correct |
80 ms |
12140 KB |
Output is correct |
3 |
Correct |
43 ms |
9036 KB |
Output is correct |
4 |
Correct |
83 ms |
11068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
10184 KB |
Output is correct |
2 |
Correct |
86 ms |
10808 KB |
Output is correct |
3 |
Correct |
69 ms |
10436 KB |
Output is correct |
4 |
Correct |
97 ms |
11876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
833 ms |
34640 KB |
Output is correct |
2 |
Incorrect |
630 ms |
27452 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
781 ms |
32368 KB |
Output is correct |
2 |
Incorrect |
654 ms |
26104 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |