제출 #540297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540297		Lyestria	사탕 분배 (IOI21_candies)	C++17	100 / 100	398 ms	34188 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 2e5+10;

ll mi[mn*4], ma[mn*4], laz[mn*4];

void prop(int x){
    if(!laz[x]) return;
    mi[x] += laz[x];
    ma[x] += laz[x];
    if(x*2+1<mn*4) {
        laz[x*2]+=laz[x];
        laz[x*2+1]+=laz[x];
    }
    laz[x]=0;
}

void eval(int x){
    prop(x*2),prop(x*2+1);
    mi[x]=min(mi[x*2],mi[x*2+1]);
    ma[x]=max(ma[x*2],ma[x*2+1]);
}

const ll inf = 0x3f3f3f3f3f3f3f3f;


#define mid ((l+r)>>1)
void update(int x,int l,int r,int a,int b,int c){
    if(l==a&&r==b)laz[x]+=c;
    else {
        prop(x);
        if(b<=mid)update(x*2,l,mid,a,b,c);
        else if(a>mid)update(x*2+1,mid+1,r,a,b,c);
        else {
            update(x*2,l,mid,a,mid,c);
            update(x*2+1,mid+1,r,mid+1,b,c);
        }
        eval(x);
    }
}

ll lv;

ll query(int x,int l,int r, ll c, ll cmin=inf, ll cmax=-inf) {
    prop(x);
    if(l==r){
        cmin = min(cmin, mi[x]);
        cmax = max(cmax, ma[x]);
        // cerr << l << " " << cmin << " " << cmax << endl;
        if(cmax-cmin<c) return lv-cmin;
        else if(cmin==mi[x]) return lv-cmax+c;
        else return lv-cmin;
    }
    else {
        prop(x*2+1);
        ll ncmin = min(cmin, mi[x*2+1]), ncmax = max(cmax,ma[x*2+1]);
        // cerr << l << " " << r << " " << ncmin << " " << ncmax << " " << ncmax-ncmin-c << endl;
        if(ncmax-ncmin<c) return query(x*2,l,mid,c,ncmin,ncmax);
        else return query(x*2+1,mid+1,r,c,cmin,cmax);
    }
}


struct event {
    int t;
    int p;
    int v;
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<event> es;
    for(int i=0;i<q;i++){
        es.push_back({i+1,l[i],v[i]});
        es.push_back({i+1,r[i]+1,-v[i]});
    }
    sort(es.begin(), es.end(), [](event a, event b){
        return a.p < b.p;
    });
    auto process = [&](const event&e){
        update(1,0,q,e.t,q,e.v);
        lv+=e.v;
    };
    vector<int> ret;
    for(int i=0,j=0;i<n;i++){
        // cerr << i << endl;
        while(j<es.size() && es[j].p<=i) process(es[j++]);
        ll ans = query(1,0,q,c[i]);
        ret.push_back(ans);
    }
    return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while(j<es.size() && es[j].p<=i) process(es[j++]);
      |               ~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33