oj.uz

답안 #483570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483570 2021-10-30T19:46:49 Z ETK 사탕 분배 (IOI21_candies) C++17
0 / 100
 135 ms 42160 KB 
#include <bits/stdc++.h>
#include "candies.h"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,m;
ll sum[N<<2],mx[N<<2],mn[N<<2];//区间和，前缀最值
struct node{int x,v;};
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)
void up(int p){
    sum[p]=sum[ls]+sum[rs];
    mx[p]=max(mx[ls],sum[ls]+mx[rs]);
    mn[p]=min(mn[ls],sum[ls]+mn[rs]);
}
void modify(int p,int L,int R,int x,int v){
    if(L>x||R<x)return;
    if(L==R){
        sum[p]+=v;
        mx[p]=mn[p]=v;
        return;
    }
    modify(ls,L,mid,x,v),modify(rs,mid+1,R,x,v);
    up(p);
}
int query(int p,int L,int R,int v,int lim){//线段树上二分
    //找到位置直接做
    if(L==R)return min((ll)lim,max(0ll,v+sum[p]));
    //若右边超限制
    if(mx[rs]-mn[rs]>=lim)return query(rs,mid+1,R,v,lim);
    //否则先做左边
    v=query(ls,L,mid,v,lim);
    //如果右边会<0
    if(v+mn[rs]<0)return sum[rs]-mn[rs];
    //如果右边会>lim
    if(v+mx[rs]>lim)return sum[rs]-(mx[rs]-lim);
    return v+sum[rs];
}
vi distribute_candies(vi c,vi l,vi r,vi v){
    n=c.size(),m=l.size();
    vi s;
    vector <node> Q[N];
    rep(i,0,m-1){
        int L=l[i],R=r[i],V=v[i];
        Q[L].pb({i+1,V}),Q[R+1].pb({i+1,-V});
    }
    rep(i,0,n-1){//扫描线
        for(auto t:Q[i]){
            modify(1,1,m,t.x,t.v);
        }
        s[i]=query(1,1,m,0,c[i]);
    }
    return s;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 135 ms 42160 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 9912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 9852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -