//
// main.cpp
//
// Created by Panagiotis Chadjicostas on
// Copyright © Panagiotis Hadjicostas. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef int ll;
typedef vector<ll> vi;
#define fo(i,a,b) for(int i = a; i<=b; i++)
#define f(i,b) for(int i=0;i<b;i++)
#define F first
#define S second
const ll MOD=ll(1e9)+7;
const ll MAXN=2*ll(1e5);
void checker(){
ll n=rand()%20+2;
vi a(n,ll());
for(ll i=0;i<n;i++){
a[i]=rand()%20+2;
}
for(ll b=0;b<(1<<n);b++){
vi on,off;
for(ll i=0;i<n;i++){
if(i&(1<<i)){
on.push_back(i);
}
else{
off.push_back(i);
}
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////
ll n;
ll seg[4*MAXN],a[MAXN],lazy[MAXN];
void Build(int node, int l, int r)
{
if(l == r)
{
seg[node] = a[l];
a[l] = node;
return;
}
int mid = (l + r) >> 1;
Build(node << 1, l, mid);
Build(node << 1 | 1, mid + 1, r);
seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
void push(ll idx,ll s,ll e){
////
if(!lazy[idx])return;
seg[idx]+=lazy[idx];
ll m=(s+e)>>1;
if(s!=e){
lazy[idx<<1]+=lazy[idx];
//seg[idx<<1]+=lazy[idx];
lazy[idx<<1|1]+=lazy[idx];
//seg[idx<<1|1]+=lazy[idx];
}
lazy[idx]=0;
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll val){
if(s>qe||e<qs){
return;
}
push(idx,s,e);
if(qs<=s&&e<=qe){
lazy[idx]+=val;
push(idx,s,e);
return;
}
ll m=(s+e)>>1;
update(s,m,qs,qe,idx<<1,val);
update(m+1,e,qs,qe,idx<<1|1,val);
seg[idx]=max(seg[idx<<1],seg[idx<<1|1]);
}
ll query(ll s,ll e,ll idx,ll val){
if(e<s)return 0;
push(idx,s,e);
if(seg[idx]<=val) return e-s+1;
//if(seg[idx]>val)return 0;
if(e-s==0)return 0;
ll m=(e+s)>>1;
return query(s,m,idx<<1,val)+query(m+1,e,idx<<1|1,val);
}
ll bs(ll idx,ll l,ll r,ll val){
if(r<l)return -1;
if(val>r)return -1;
push(idx,l,r);
if(r-l==0)return seg[idx];
ll m=(l+r)>>1;
if(val<=m){
return bs(idx<<1,l,m,val);
}
else{
return bs(idx<<1|1,m+1,r,val);
}
}
void upd(){
ll c,h;cin>>c>>h;
ll left=query(0,n-1,1,h-1);
//cout<<left<<endl;
ll val=bs(1,0,n-1,left+c-1);
//cout<<val<<endl;
ll r1=query(0,n-1,1,val-1),r2=query(0,n-1,1,val);
//cout<<r1<<' '<<r2<<endl;
update(0,n,left,r1-1,1,1);
ll tmp=c+left-r1;
update(0,n-1,max(r1+1,r2-tmp+1)-1,r2-1,1,1);
}
void qur(){
ll l,r;
cin>>l>>r;
cout<<query(0,n-1,1,r)-query(0,n-1,1,l-1)<<endl;
}
void solve(){
ll q;cin>>n>>q;
//vi a(n,ll());
f(i,n){
cin>>a[i];
}
sort(a,a+n);
Build(1,0,n-1);
//cout<<seg[2]<<endl;
for(ll queries=1;queries<=q;queries++){
char type;cin>>type;
if(type=='F'){
upd();
}
else{
qur();
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;//cin>>t;
while (t--) {
solve();
}
return 0;
}
Compilation message
grow.cpp: In function 'void push(ll, ll, ll)':
grow.cpp:77:8: warning: unused variable 'm' [-Wunused-variable]
77 | ll m=(s+e)>>1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
2464 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
864 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
1484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
2412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1028 ms |
2380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
2388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
2360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
2356 KB |
Time limit exceeded |
