oj.uz

답안 #466712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466712 2021-08-20T13:28:25 Z Urvuk3 Watering can (POI13_kon) C++17
100 / 100
 449 ms 29684 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MAXN=3e5+5,MAXM=40,INF=1e9,MOD=1e9+7;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define PRINTBITS(x) {bitset<5> f=x; cerr<<#x<<'-'<<f<<endl<<flush;}
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back

ll N,m,K,q,x,y,z,res=0,l,r;
string s,t;
vector<int> a;

int lazy[4*MAXN];
pii seg[4*MAXN]; // cuvacu par gde je druga vrdnost index maximuma
int BIT[MAXN];

void propagate(int node,int l,int r){
    seg[node].fi+=lazy[node];
    if(l<r){
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}

void update(int node,int l,int r,int L,int R,int val){
    propagate(node,l,r);
    if(l>r  || l>R || r<L) return;
    if(L<=l && r<=R){
        lazy[node]+=val;
        propagate(node,l,r);
        return;
    }
    update(2*node,l,mid,L,R,val);
    update(2*node+1,mid+1,r,L,R,val);
    seg[node]=max(seg[2*node],seg[2*node+1]);
}

pii query(int node,int l,int r,int L,int R){
    propagate(node,l,r);
    if(l>r || l>R || r<L) return {-INF,-INF};
    if(L<=l && r<=R) return seg[node];
    return max(query(2*node,l,mid,L,R),query(2*node+1,mid+1,r,L,R));
}

void updateBIT(int idx){
    while(idx<MAXN){
        BIT[idx]++;
        idx+=idx&-idx;
    }
}

int queryBIT(int idx){
    int ret=0;
    while(idx){
        ret+=BIT[idx];
        idx-=idx&-idx;
    }
    return ret;
}

int queryBIT(int a,int b){
    return queryBIT(b)-queryBIT(a-1);
}

void init(int node,int l,int r){
    if(l==r){
        if(a[l]>=K){
            seg[node]={-INF,-INF};
            updateBIT(l);
        }
        else{
            seg[node]={a[l],l};
        }
        return;
    }
    init(2*node,l,mid); init(2*node+1,mid+1,r);
    seg[node]=max(seg[2*node],seg[2*node+1]);
}

void inicjuj(int n, int k, int *D){
    K=k;
    N=n;
    a.pb(INF);
    for(int i=1;i<=N;i++){
        a.pb(D[i-1]);
    }
    init(1,1,N);
}

void podlej(int a, int b){
    ++a; ++b;
    update(1,1,N,a,b,+1);
    while(seg[1].fi>=K){
        updateBIT(seg[1].se);
        update(1,1,N,seg[1].se,seg[1].se,-INF);
    }
}

int dojrzale(int a, int b){
    ++a; ++b;
    return queryBIT(a,b);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 4 ms 1612 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 3084 KB Output is correct
2 Correct 51 ms 4168 KB Output is correct
3 Correct 42 ms 4164 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 3884 KB Output is correct
2 Correct 88 ms 5952 KB Output is correct
3 Correct 79 ms 5920 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 5936 KB Output is correct
2 Correct 77 ms 8496 KB Output is correct
3 Correct 106 ms 7328 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 6728 KB Output is correct
2 Correct 119 ms 10716 KB Output is correct
3 Correct 212 ms 11452 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 6828 KB Output is correct
2 Correct 206 ms 14624 KB Output is correct
3 Correct 206 ms 12660 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 10812 KB Output is correct
2 Correct 344 ms 17848 KB Output is correct
3 Correct 400 ms 20920 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 17860 KB Output is correct
2 Correct 298 ms 28208 KB Output is correct
3 Correct 384 ms 27472 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 17968 KB Output is correct
2 Correct 324 ms 29684 KB Output is correct
3 Correct 449 ms 27792 KB Output is correct