oj.uz

답안 #390600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390600 2021-04-16T11:01:03 Z PanTkd Growing Trees (BOI11_grow) C++14
0 / 100
 1000 ms 2464 KB 
//
//  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;
      |        ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 2464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 1484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 2412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1028 ms 2380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1051 ms 2388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 2360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 2356 KB Time limit exceeded