Submission #65067416

---

Source Code Expand

#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#define x first
#define y second

vi v;
vplli L,R;
int ccw(plli a,plli b,plli c) {
    return (__int128) (b.x-a.x)*(c.y-a.y) >= (__int128) (b.y-a.y)*(c.x-a.x);
}
vplli parHull(vplli v) {
    vplli hull;
    sort(v.begin(),v.end());
    for (auto p: v) {
        if (!hull.empty() && (p.x == hull.back().x)) continue;
        while (!hull.empty() && (p.y == hull.back().y)) hull.pop_back();
        hull.pb(p);
    }
    return hull;
}
LLI f[3000005];
typedef long long ll;
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};
int main() {
    int N,K;
    string S;
    cin >> N >> K >> S;

    int i,c = 0;
    LLI area = 0;
    L.pb(mp(0,0));
    for (i = 0; i < S.size(); i++) {
        int o = c;
        c += (S[i] == 'A') ? 1:-1;
        if (o < 0) area += (-o+1)/2;
        if (o > 0) f[o-1]++;
        if (c >= 0) L.pb(mp(c,area));
    }
    c = area = 0;
    R.pb(mp(0,0));
    reverse(S.begin(),S.end());
    for (i = 0; i < S.size(); i++) {
        int o = c;
        c += (S[i] == 'C') ? 1:-1;
        if (o < 0) area += (-o+1)/2;
        if (c >= 0) R.pb(mp(c,area));
    }
    for (i = N+2; i >= 0; i--) f[i] += f[i+2];
    for (i = N+2; i >= 0; i--) f[i] += f[i+1];

    L = parHull(L),R = parHull(R);
    LineContainer hull;
    for (plli a: L) {
        for (plli b: R) {
            hull.add(-f[a.x+b.x],-(a.y+b.y));
        }
    }

    for (i = 1; i <= K; i++) printf("%lld\n",-hull.query(i));
    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:115:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  115 |     for (i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~
Main.cpp:125:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  125 |     for (i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

Judge Result