Submission #1100080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100080		Andrey	Nile (IOI24_nile)	C++17	100 / 100	264 ms	42544 KiB

nile

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

vector<long long> big0(500001,-1e18);
vector<long long> big1(500001,-1e18);
vector<long long> seg0(500001,-1e18);
vector<long long> seg1(500001,-1e18);
vector<long long> haha(500001);
vector<long long> pr(500001);
long long n;

void build(long long l, long long r, long long x) {
    if(l == r) {
        if(l%2) {
            big1[x] = haha[l];
        }
        else {
            big0[x] = haha[l];
        }
        return;
    }
    long long mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    big0[x] = max(big0[x*2],big0[x*2+1]);
    big1[x] = max(big1[x*2],big1[x*2+1]);

}

void upd(long long l, long long r, long long x, long long p, long long br) {
    if(l == r) {
        if(l%2) {
            seg1[x] = br;
        }
        else {
            seg0[x] = br;
        }
        return;
    }
    long long mid = (l+r)/2;
    if(p <= mid) {
        upd(l,mid,x*2,p,br);
    }
    else {
        upd(mid+1,r,x*2+1,p,br);
    }
    seg0[x] = max(seg0[x*2],seg0[x*2+1]);
    seg1[x] = max(seg1[x*2],seg1[x*2+1]);
}

long long calc(long long l, long long r, long long ql, long long qr, long long x, bool y, bool z) {
    if(qr < ql) {
        return -1e18;
    }
    if(l == ql && r == qr) {
        if(y) {
            if(z) {
                return big1[x];
            }
            else {
                return big0[x];
            }
        }
        else {
            if(z) {
                return seg1[x];
            }
            else {
                return seg0[x];
            }
        }
    }
    long long mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,x*2,y,z);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,x*2+1,y,z);
    }
    else {
        return max(calc(l,mid,ql,mid,x*2,y,z),calc(mid+1,r,mid+1,qr,x*2+1,y,z));
    }
}

long long dude(long long l, long long r) {
    if(r < l) {
        return 0;
    }
    long long ans = pr[r]-pr[l-1];
    long long c = max(calc(1,n,l,r,1,1,l%2),calc(1,n,l,r,1,0,(l+1)%2));
    if((r-l+1)%2 == 0) {
        c = 0;
    }
    return ans-c;
}

std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {
    vector<pair<long long,long long>> wut(1,{0,0});
    n = w.size();
    for(long long i = 0; i < w.size(); i++) {
        wut.push_back({w[i],i});
    }
    sort(wut.begin(),wut.end());
    for(long long i = 1; i <= n; i++) {
        haha[i] = b[wut[i].second]-a[wut[i].second];
        pr[i] = b[wut[i].second]+pr[i-1];
    }
    build(1,n,1);
    vector<long long> ans(e.size());
    vector<pair<long long,long long>> no(0);
    for(long long i = 0; i < e.size(); i++) {
        no.push_back({e[i],i});
    }
    sort(no.begin(),no.end());
    long long sb = 0;
    for(long long i = 0; i < a.size(); i++) {
        sb+=a[i];
    }
    vector<pair<long long,pair<long long,long long>>> wow(0);
    for(long long i = 2; i <= n; i++) {
        wow.push_back({wut[i].first-wut[i-1].first,{0,i-1}});
        if(i > 2) {
            wow.push_back({wut[i].first-wut[i-2].first,{1,i-2}});
        }
    }
    upd(1,n,1,1,haha[1]);
    upd(1,n,1,n,haha[n]);
    sort(wow.begin(),wow.end());
    set<long long> idk;
    for(long long i = 0; i <= w.size(); i++) {
        idk.insert(i);
    }
    long long y = 0;
    for(long long i = 0; i < wow.size(); i++) {
        while(y < no.size() && no[y].first < wow[i].first) {
            ans[no[y].second] = sb;
            y++;
        }
        long long p = wow[i].second.second;
        if(wow[i].second.first) {
            p++;
            long long l = *(--idk.upper_bound(p)),r = *idk.lower_bound(p);
            sb-=dude(l+1,r);
            upd(1,n,1,p,b[wut[p].second]-a[wut[p].second]);
            sb+=dude(l+1,r);
        }
        else {
            idk.erase(p);
            long long l = *(--idk.upper_bound(p)),r = *idk.lower_bound(p);
            sb-=dude(l+1,p);
            sb-=dude(p+1,r);
            sb+=dude(l+1,r);
        }
    }
    for(long long i = y; i < no.size(); i++) {
        ans[no[i].second] = sb;
    }
    return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:101:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(long long i = 0; i < w.size(); i++) {
      |                          ~~^~~~~~~~~~
nile.cpp:112:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(long long i = 0; i < e.size(); i++) {
      |                          ~~^~~~~~~~~~
nile.cpp:117:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(long long i = 0; i < a.size(); i++) {
      |                          ~~^~~~~~~~~~
nile.cpp:131:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(long long i = 0; i <= w.size(); i++) {
      |                          ~~^~~~~~~~~~~
nile.cpp:135:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(long long i = 0; i < wow.size(); i++) {
      |                          ~~^~~~~~~~~~~~
nile.cpp:136:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         while(y < no.size() && no[y].first < wow[i].first) {
      |               ~~^~~~~~~~~~~
nile.cpp:156:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(long long i = y; i < no.size(); i++) {
      |                          ~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18