oj.uz

답안 #466705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466705 2021-08-20T11:31:20 Z Urvuk3 Watering can (POI13_kon) C++17
0 / 100
 515 ms 16676 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 seg1[4*MAXN]; // cuvacu par gde je druga vrdnost index maximuma
int seg2[4*MAXN]; // cuvacu 1 u listu ako je drvo zrelo

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

void update1(int node,int l,int r,int L,int R,int val){
    propagate1(node,l,r);
    if(l>r || l>R || r<L) return;
    if(L<=l && r<=R){
        lazy[node]+=val;
        propagate1(node,l,r);
        return;
    }
    update1(2*node,l,mid,L,R,val);
    update1(2*node+1,mid+1,r,L,R,val);
    seg1[node].fi=max(seg1[2*node].fi,seg1[2*node+1].fi);
}

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

void update2(int node,int l,int r,int idx){
    if(l==r){
        seg2[node]++;
        return;
    }
    if(idx<=mid) update2(2*node,l,mid,idx);
    else update2(2*node+1,mid+1,r,idx);
    seg2[node]=seg2[2*node]+seg2[2*node+1];
}

int query2(int node,int l,int r,int L,int R){
    if(L<=l && r<=R) return seg2[node];
    ll ret=0;
    if(L<=mid) ret+=query2(node,l,mid,L,R);
    if(R>mid) ret+=query2(node,mid+1,r,L,R);
    return ret;
}

void init(int node,int l,int r){
    if(l==r){
        seg1[node]={a[l],l};
        seg2[node]=(a[l]>=K);
        return;
    }
    init(2*node,l,mid);
}

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]);
    }
    init(1,1,N);
}

void podlej(int a, int b){
    update1(1,1,N,a,b,1);
    while(true){
        pii qu=query1(1,1,N,a,b);
        if(qu.fi<K) break;
        update2(1,1,N,qu.se);
        update1(1,1,N,qu.se,qu.se,-INF);
    }
}

int dojrzale(int a, int b){
    return query2(1,1,N,a,b);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 3680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 5448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 259 ms 6052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 296 ms 6180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 393 ms 9976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 503 ms 16548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 515 ms 16676 KB Output isn't correct
2 Halted 0 ms 0 KB -