Submission #1001288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001288		Andrey	Distributing Candies (IOI21_candies)	C++17	0 / 100	204 ms	52820 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> seg(1000001);
vector<pair<long long,long long>> wow(1000001);
long long d;

void build(long long l, long long r, long long x) {
    seg[x] = {0,d-1};
    wow[x] = {0,0};
    if(l == r) {
        return;
    }
    long long m = (l+r)/2;
    build(l,m,x*2);
    build(m+1,r,x*2+1);
}

void upd(long long l, long long r, long long x, long long p, long long br) {
    if(l == r) {
        if(br == LLONG_MAX) {
            seg[x] = {0,d-1};
            wow[x] = {0,0};
        }
        else {
            if(br > 0) {
                seg[x] = {min(br,d-1),d-1};
                wow[x] = {0,min(br,d-1)};
            }
            else {
                seg[x] = {0,max(0LL,d-1+br)};
                wow[x] = {min(-br,d-1),0};
            }
        }
        return;
    }
    long long m = (l+r)/2;
    if(p <= m) {
        upd(l,m,x*2,p,br);
    }
    else {
        upd(m+1,r,x*2+1,p,br);
    }
    long long al,ar;
    if(wow[x*2+1].first >= seg[x*2].first) {
        al = seg[x*2+1].first;
    }
    else {
        al = min(seg[x*2+1].second,seg[x*2+1].first+seg[x*2].first-wow[x*2+1].first);
    }
    if(wow[x*2+1].second >= d-1-seg[x*2].second) {
        ar = seg[x*2+1].second;
    }
    else {
        ar = max(seg[x*2+1].first,seg[x*2+1].second-(d-1-seg[x*2].second-wow[x*2+1].second));
    }
    seg[x] = {al,ar};
    wow[x] = {wow[x*2+1].first+seg[x*2+1].first-al,wow[x*2+1].second+ar-seg[x*2+1].second};
}

void dude(int l, int r, int x) {
    cout << l << " " << r << " " << seg[x].first << " " << seg[x].second << endl;
    if(l == r) {
        return;
    }
    int m = (l+r)/2;
    dude(l,m,x*2);
    dude(m+1,r,x*2+1);
}

vector<pair<int,int>> haha[300000];

vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) {
    long long n = c.size(),q = l.size();
    d = c[0]+1;
    build(0,q-1,1);
    for(long long i = 0; i < q; i++) {
        haha[l[i]].push_back({v[i],i});
        haha[r[i]+1].push_back({LLONG_MAX,i});
    }
    vector<int> ans(n);
    for(long long i = 0; i < n; i++) {
        for(long long j = 0; j < haha[i].size(); j++) {
            upd(0,q-1,1,haha[i][j].second,haha[i][j].first);
        }
        ans[i] = seg[1].first;
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:84:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(long long j = 0; j < haha[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~

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