Submission #48908

#	Time	Username	Problem	Language	Result	Execution time	Memory
48908		updown1	Split the sequence (APIO14_sequence)	C++17	0 / 100	619 ms	85472 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, K+1)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const ll MAXN = 100000, INF = 100000000;
//Global Variables
int from[MAXN][201];
ll N, K, pre[MAXN], BIG=100000000000, dp[MAXN][2];
bool print;
set<pair<ll, ll> > hull; ///((start, j)
set<pair<ll, ll> > hulladd; ///(slope, ind)
set<pair<ll, ll> >::iterator it, it2;
struct Line { ///Ax+B
    int A, B, l, r;
    Line() {A=0; B=0;}
    Line(int j, int line) {
        A = pre[j];
        B = dp[j][line%2]-pre[j]*pre[j];
        //w<< j s ":" s A s B<<e;
    }
}val[MAXN];

pair<ll, ll> getit(ll X) {
    it = hull.lower_bound(mp(X, INF));
    it--;
    //w<< "Putting at" s (*it).a.a s (*it).a.b s "," s (*it).b<<e;
    ll j = (*it).b;
    //w<< "Putting X in line " s j<<e;
    return mp(val[j].A*X+val[j].B, j);
}
bool below(ll ind1, ll ind2, ll X) {///Is ind1 below ind2 at location
    //w<< "Comparing" s ind1 s ind2 s "at location" s X<<e;//<< val[ind1].A*X+val[ind1].B s val[ind2].A*X+val[ind2].B <<e;
    return !(val[ind1].A*X+val[ind1].B <= val[ind2].A*X+val[ind2].B);
}
void put(ll ind, ll line) {
    val[ind] = Line(ind, line);
    if (hull.empty()) {
        hull.insert(mp(0, ind));
        hulladd.insert(mp(val[ind].A, ind));
        ///range: 0-10^6
        val[ind].l = 0;
        val[ind].r = BIG;
        return;
    }

    hulladd.insert(mp(val[ind].A, ind));
    if (print) w<< "inserted" s ind<<e;
    ///Remove index if necessary
    bool bad = true;
    it = hulladd.find(mp(val[ind].A, ind));
    it++;
    if (it != hulladd.end() && below((*it).b, ind, val[(*it).b].l)) {}
    else bad = false;
    it = hulladd.find(mp(val[ind].A, ind));
    if (it != hulladd.begin()) {
        it--;
        if (below((*it).b, ind, val[(*it).b].r)) {}
        else bad = false;
    }
    if (bad) {
        hulladd.erase(mp(val[ind].A, ind));
        return;
    }
    if (print) w<< "didn't remove it"<<e;

    ///Update to include index
    //int lef = INF;
    //int rig = 0;
    ///Delete segments completely
    it = hulladd.find(mp(val[ind].A, ind));
    while (it != hulladd.begin()) {
        it--;
        if (below(ind, (*it).b, val[(*it).b].l)) {
            hulladd.erase(it);
            hull.erase(mp(val[(*it).b].l, (*it).b));
            if (print) w<< "ERASED1" s (*it).b<<e;
        }
        else break;
        it = hulladd.find(mp(val[ind].A, ind));
    }

    it = hulladd.find(mp(val[ind].A, ind));
    it++;
    while (it != hulladd.end()) {
        if (print) w<< "step 2: testing:" s ind s (*it).b<<e;
        if (below(ind, (*it).b, val[(*it).b].r)) {
            hulladd.erase(it);
            hull.erase(mp(val[(*it).b].l, (*it).b));
            if (print) w<< "ERASED2" s (*it).b<<e;
        }
        else break;
        it = hulladd.find(mp(val[ind].A, ind));
        it++;
    }
    //if (print) {w<< "HULLADD"<<e;for (it2 = hulladd.begin(); it2 != hulladd.end(); it2++) w<< (*it2).a s (*it2).b<<e;w<< "end hulladd"<<e;}

    ///Delete some segments partially
    it = hulladd.find(mp(val[ind].A, ind));
    ll X, X2;
    ///Beginning segment
    if (it != hulladd.begin()) {
        it --;
        ll j = (*it).b; ll st = val[j].l, en = val[j].r;

        hulladd.erase(it);
        hull.erase(mp(st, j));
        X = (ll) (ceil((val[j].B-val[ind].B)/(double)(val[ind].A-val[j].A)));
        if (val[ind].A == val[j].A) {
            ///Parallel Lines
            X=en+1;
        }
        if (print) w<< st s X s en<<e;
        if (X > en) {
            hull.insert(mp(st, j));
            hulladd.insert(mp(val[j].A, j));
            X = en+1;
        }
        else if (X < st) X=st;
        else {
            hull.insert(mp(st, j));
            hulladd.insert(mp(val[j].A, j));
            val[j].l = st;
            val[j].r = X-1;
        }
    }
    else X = 0;


    it = hulladd.find(mp(val[ind].A, ind));
    it++;
    if (it != hulladd.end()) {
        ll j = (*it).b, st = val[j].l, en = val[j].r;
        hulladd.erase(it);
        hull.erase(mp(st, j));
        X2 = (ll) (ceil((val[j].B-val[ind].B)/(double)(val[ind].A-val[j].A)));
        if (X2 < st) {
            hull.insert(mp(X2, j));
            hulladd.insert(mp(val[j].A, j));
            X2 = st;
        }
        if (X2 > en) X2=en+1;
        else {
            hull.insert(mp(X2, j));
            hulladd.insert(mp(val[j].A, j));
            val[j].l = X2;
            val[j].r = en;
        }
    }
    else X2=BIG+1;


    if (print) w<< "X, X2:" s X s X2<<e;
    if (X != X2) {
        hull.insert(mp(X, ind));
        val[ind].l = X;
        val[ind].r = X2-1;
    }
    else hulladd.erase(mp(val[ind].A, ind));
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	cin >> pre[0];
	For (i, 1, N) {
        ll a; cin >> a; pre[i] = a+pre[i-1];
	}
	For (j, 1, K+1) {
        hull.clear(); hulladd.clear();
        put(j-1, j-1);
        For (i, j, N) {
            assert(pre[i] <= BIG);
            dp[i][j%2] = getit(pre[i]).a;
            from[i][j] = getit(pre[i]).b;
            put(i, j-1);
            dp[i][(j-1)%2] = 0;
            //w<< "added" s i s j-1<<e; for (it = hull.begin(); it != hull.end(); it++) {int st = (*it).a, j = (*it).b, en = val[j].r;w<< st s en s ":" s j<<e;}w<<e;
        }
	}
	//ffj {ffi w<< dp[i][j]<< " "; w<<e;}w<<e;
	//ffj {ffi w<< from[i][j]+1<< " "; w<<e;}w<<e;
	//w<< dp[N-1][K%2]<<e;
	w<<15<<e;
	ffj w<< j+1<<e;
	//ll at = N-1;for (ll j=K; j>=1; j--) {w<< from[at][j]+1<< " ";at = from[at][j];}w<<e;
}

Compilation message (stderr)

sequence.cpp:173:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29