fork download

copy

#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
int fdiv(int a, int32_t b)
{ // floored division
    return a / b - ((a ^ b) < 0 && a % b);
}
struct line
{
    int32_t m;
    long long c;
    long long eval(long long x)
    {
        return m * x + c;
    }
    long long intersectX(line l)
    {
        return fdiv(c - l.c, l.m - m);
    }
    bool operator<(const line &x) const
    {
        if (m == x.m)
            return c > x.c;
        return m > x.m;
    }
};
struct Static_CHT
{
    vector<line> lines;
    vector<int> isects;
    Static_CHT()
    {
    }
    Static_CHT(vector<line> p)
    {
        sort(p.begin(), p.end());
        for (int i = 0; i < p.size(); i++)
        {
            line cur = p[i];
            while (lines.size() >= 2 &&
                   cur.intersectX(lines.back()) >= lines.back().intersectX(lines[lines.size() - 2]))
                lines.pop_back();
            lines.push_back(cur);
        }
        reverse(lines.begin(), lines.end());
        isects.resize(max(0ll, (int)lines.size() - 1));
        for (int i = 0; i < isects.size(); i++)
            isects[i] = this->lines[i].intersectX(this->lines[i + 1]);
    }
    int idx = 0;
    int Query(int x)
    {
        if (!lines.size())
            return -3e18;
        while (idx < isects.size() && isects[idx] < x)
            idx++;
        return lines[idx].eval(x);
    }
};
const int NM = 100000;
const int B = 320;
Static_CHT MIN[NM / B + 1];
Static_CHT MAX[NM / B + 1];
Static_CHT GSS[NM / B + 1];
Static_CHT LSS[NM / B + 1];
int LSS_CACHE[NM / B + 1];
int GSS_CACHE[NM / B + 1];
int MAX_CACHE[NM / B + 1];
int MIN_CACHE[NM / B + 1];
bool use_CHT[NM / B + 1];
struct Data
{
    int gs, ls, mn, mx;
};
Data CACHE[NM / B + 1];
int n;
int lz_b[NM / B + 1], lz_c[NM / B + 1];
vector<int> pfs, op;
void restore(const int blk)
{
    use_CHT[blk] = 1;
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
        pfs[i] = op[i];
}
int LS(const int blk)
{
    if (use_CHT[blk])
        return (lz_b[blk] == 0 ? LSS_CACHE[blk] : -LSS[blk].Query(lz_b[blk]));
    else
        return CACHE[blk].ls;
}
int GS(const int blk)
{
    if (use_CHT[blk])
        return (lz_b[blk] == 0 ? GSS_CACHE[blk] : GSS[blk].Query(lz_b[blk]));
    else
        return CACHE[blk].gs;
}
int MN(const int blk)
{
    if (use_CHT[blk])
        return lz_c[blk] + (lz_b[blk] == 0 ? MIN_CACHE[blk] : -MIN[blk].Query(lz_b[blk]));
    else
        return CACHE[blk].mn;
}
int MX(const int blk)
{
    if (use_CHT[blk])
        return lz_c[blk] + (lz_b[blk] == 0 ? MAX_CACHE[blk] : MAX[blk].Query(lz_b[blk]));
    else
        return CACHE[blk].mx;
}
void recomp(int blk)
{
    CACHE[blk].gs = CACHE[blk].mx = -1e18;
    CACHE[blk].ls = CACHE[blk].mn = 1e18;
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
    {
        if (i != blk * B)
        {
            CACHE[blk].gs = max(CACHE[blk].gs, pfs[i] - CACHE[blk].mn);
            CACHE[blk].ls = min(CACHE[blk].ls, pfs[i] - CACHE[blk].mx);
        }
        CACHE[blk].mx = max(CACHE[blk].mx, pfs[i]);
        CACHE[blk].mn = min(CACHE[blk].mn, pfs[i]);
    }
}
void add_range(int l, int r, const int b, const int c)
{
    if (l > r)
        return;
    if (l / B != r / B)
    {
        use_CHT[l / B] = 0;
        for (int i = l; i < (l / B + 1) * B; i++)
            pfs[i] += b * i + c;
        if (r != n)
        {
            use_CHT[r / B] = 0;
            for (int i = r / B * B; i <= r; i++)
                pfs[i] += b * i + c;
            for (int i = l / B + 1; i < r / B; i++)
                lz_b[i] += b, lz_c[i] += c;
        }
        else
        {
            for (int i = l / B + 1; i <= r / B; i++)
                lz_b[i] += b, lz_c[i] += c;
        }
    }
    else
    {
        use_CHT[l / B] = 0;
        for (int i = l; i <= r; i++)
            pfs[i] += b * i + c;
    }
}
struct Query
{
    int u, v, c, id;
};
void Yoshi()
{
    int q;
    cin >> n >> q;
    vector<int> p(n);
    for (auto &i : p)
        cin >> i;
    pfs.resize(n + 1);
    for (int i = 0; i < n; i++)
        pfs[i + 1] = pfs[i] + p[i];
    op = pfs;
    for (int i = 0; i <= n; i += B)
    {
        vector<line> mn, mx, gsx, lsx;
        vector<int> lss(B, 1e18), gss(B, -1e18);
        for (int j = i; j < min(n + 1, i + B); j++)
        {
            mn.push_back({(int32_t)-j, -pfs[j]});
            mx.push_back({(int32_t)j, pfs[j]});
        }
        for (int j = i; j < min(n + 1, i + B); j++)
            for (int k = j + 1; k < min(n + 1, i + B); k++)
            {
                lss[k - j] = min(lss[k - j], pfs[k] - pfs[j]);
                gss[k - j] = max(gss[k - j], pfs[k] - pfs[j]);
            }
        for (int i = 1; i < B; i++)
        {
            lsx.push_back({(int32_t)-i, -lss[i]});
            gsx.push_back({(int32_t)i, gss[i]});
        }
        MIN[i / B] = mn;
        MAX[i / B] = mx;
        LSS[i / B] = lsx;
        GSS[i / B] = gsx;
        MIN_CACHE[i / B] = -MIN[i / B].Query(0);
        MAX_CACHE[i / B] = MAX[i / B].Query(0);
        LSS_CACHE[i / B] = -LSS[i / B].Query(0);
        GSS_CACHE[i / B] = GSS[i / B].Query(0);
        GSS[i / B].idx = 0;
        LSS[i / B].idx = 0;
        MIN[i / B].idx = 0;
        MAX[i / B].idx = 0;
    }
    fill(use_CHT, use_CHT + NM / B + 1, 1);
    vector<int> qres(q);
    vector<Query> queries;
    for (int id = 0; id < q; id++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        queries.push_back({u, v, c, id});
    }
    sort(queries.begin(), queries.end(), [](Query &a, Query &b) { return a.c < b.c; });
    for (auto &[u, v, c, id] : queries)
    {
        add_range(u, v, c, -c * (u - 1));
        add_range(v + 1, n, 0, c * (v - u + 1));
        int gs = -1e18, ls = 1e18;
        int mib = 1e18, mxib = -1e18;
        for (int i = 0; i <= NM / B; i++)
            if (!use_CHT[i])
                recomp(i);
        for (int i = 0; i <= NM / B; i++)
        {
            gs = max(gs, GS(i));
            ls = min(ls, LS(i));
            const int mx = MX(i), mn = MN(i);
            if (i)
            {
                gs = max(mx - mib, gs);
                ls = min(mn - mxib, ls);
            }
            mib = min(mib, mn);
            mxib = max(mxib, mx);
        }
        qres[id] = max(abs(gs), abs(ls));
        for (int i = 0; i <= NM / B; i++)
            if (!use_CHT[i])
                restore(i);
        for (int i = u / B; i <= n / B; i++)
            lz_b[i] = lz_c[i] = 0;
    }
    for (auto &i : qres)
        cout << i << endl;
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}
 

Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:3: error: illegal character: '#'
#define int long long
^
Main.java:3: error: class, interface, or enum expected
#define int long long
        ^
Main.java:4: error: illegal character: '#'
#ifndef yoshi_likes_e4
^
Main.java:5: error: illegal character: '#'
#define endl '\n'
^
Main.java:6: error: illegal character: '#'
#endif
^
Main.java:7: error: illegal character: '#'
#define problem ""
^
Main.java:8: error: illegal character: '#'
#define multitest 0
^
Main.java:9: error: illegal character: '#'
#define debug(x) cerr << #x << " = " << x << endl;
^
Main.java:9: error: illegal character: '#'
#define debug(x) cerr << #x << " = " << x << endl;
                         ^
Main.java:10: error: class, interface, or enum expected
void init()
^
Main.java:16: error: class, interface, or enum expected
}
^
Main.java:20: error: class, interface, or enum expected
    long long c;
    ^
Main.java:21: error: class, interface, or enum expected
    long long eval(long long x)
    ^
Main.java:24: error: class, interface, or enum expected
    }
    ^
Main.java:28: error: class, interface, or enum expected
    }
    ^
Main.java:33: error: class, interface, or enum expected
        return m > x.m;
        ^
Main.java:34: error: class, interface, or enum expected
    }
    ^
Main.java:36: error: class, interface, or enum expected
struct Static_CHT
^
Main.java:39: error: class, interface, or enum expected
    vector<int> isects;
    ^
Main.java:40: error: class, interface, or enum expected
    Static_CHT()
    ^
Main.java:46: error: class, interface, or enum expected
        for (int i = 0; i < p.size(); i++)
        ^
Main.java:46: error: class, interface, or enum expected
        for (int i = 0; i < p.size(); i++)
                        ^
Main.java:46: error: class, interface, or enum expected
        for (int i = 0; i < p.size(); i++)
                                      ^
Main.java:49: error: class, interface, or enum expected
            while (lines.size() >= 2 &&
            ^
Main.java:52: error: class, interface, or enum expected
            lines.push_back(cur);
            ^
Main.java:53: error: class, interface, or enum expected
        }
        ^
Main.java:55: error: class, interface, or enum expected
        isects.resize(max(0ll, (int)lines.size() - 1));
        ^
Main.java:56: error: class, interface, or enum expected
        for (int i = 0; i < isects.size(); i++)
        ^
Main.java:56: error: class, interface, or enum expected
        for (int i = 0; i < isects.size(); i++)
                        ^
Main.java:56: error: class, interface, or enum expected
        for (int i = 0; i < isects.size(); i++)
                                           ^
Main.java:58: error: class, interface, or enum expected
    }
    ^
Main.java:60: error: class, interface, or enum expected
    int Query(int x)
    ^
Main.java:64: error: class, interface, or enum expected
        while (idx < isects.size() && isects[idx] < x)
        ^
Main.java:66: error: class, interface, or enum expected
        return lines[idx].eval(x);
        ^
Main.java:67: error: class, interface, or enum expected
    }
    ^
Main.java:69: error: class, interface, or enum expected
const int NM = 100000;
^
Main.java:70: error: class, interface, or enum expected
const int B = 320;
^
Main.java:71: error: class, interface, or enum expected
Static_CHT MIN[NM / B + 1];
^
Main.java:72: error: class, interface, or enum expected
Static_CHT MAX[NM / B + 1];
^
Main.java:73: error: class, interface, or enum expected
Static_CHT GSS[NM / B + 1];
^
Main.java:74: error: class, interface, or enum expected
Static_CHT LSS[NM / B + 1];
^
Main.java:75: error: class, interface, or enum expected
int LSS_CACHE[NM / B + 1];
^
Main.java:76: error: class, interface, or enum expected
int GSS_CACHE[NM / B + 1];
^
Main.java:77: error: class, interface, or enum expected
int MAX_CACHE[NM / B + 1];
^
Main.java:78: error: class, interface, or enum expected
int MIN_CACHE[NM / B + 1];
^
Main.java:79: error: class, interface, or enum expected
bool use_CHT[NM / B + 1];
^
Main.java:80: error: class, interface, or enum expected
struct Data
^
Main.java:83: error: class, interface, or enum expected
};
^
Main.java:84: error: class, interface, or enum expected
Data CACHE[NM / B + 1];
^
Main.java:85: error: class, interface, or enum expected
int n;
^
Main.java:86: error: class, interface, or enum expected
int lz_b[NM / B + 1], lz_c[NM / B + 1];
^
Main.java:87: error: class, interface, or enum expected
vector<int> pfs, op;
^
Main.java:88: error: class, interface, or enum expected
void restore(const int blk)
^
Main.java:91: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
    ^
Main.java:91: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
                          ^
Main.java:91: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
                                                         ^
Main.java:93: error: class, interface, or enum expected
}
^
Main.java:98: error: class, interface, or enum expected
    else
    ^
Main.java:100: error: class, interface, or enum expected
}
^
Main.java:105: error: class, interface, or enum expected
    else
    ^
Main.java:107: error: class, interface, or enum expected
}
^
Main.java:112: error: class, interface, or enum expected
    else
    ^
Main.java:114: error: class, interface, or enum expected
}
^
Main.java:119: error: class, interface, or enum expected
    else
    ^
Main.java:121: error: class, interface, or enum expected
}
^
Main.java:125: error: class, interface, or enum expected
    CACHE[blk].ls = CACHE[blk].mn = 1e18;
    ^
Main.java:126: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
    ^
Main.java:126: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
                          ^
Main.java:126: error: class, interface, or enum expected
    for (int i = blk * B; i < min((blk + 1) * B, n + 1); i++)
                                                         ^
Main.java:131: error: class, interface, or enum expected
            CACHE[blk].ls = min(CACHE[blk].ls, pfs[i] - CACHE[blk].mx);
            ^
Main.java:132: error: class, interface, or enum expected
        }
        ^
Main.java:134: error: class, interface, or enum expected
        CACHE[blk].mn = min(CACHE[blk].mn, pfs[i]);
        ^
Main.java:135: error: class, interface, or enum expected
    }
    ^
Main.java:141: error: class, interface, or enum expected
    if (l / B != r / B)
    ^
Main.java:144: error: class, interface, or enum expected
        for (int i = l; i < (l / B + 1) * B; i++)
        ^
Main.java:144: error: class, interface, or enum expected
        for (int i = l; i < (l / B + 1) * B; i++)
                        ^
Main.java:144: error: class, interface, or enum expected
        for (int i = l; i < (l / B + 1) * B; i++)
                                             ^
Main.java:146: error: class, interface, or enum expected
        if (r != n)
        ^
Main.java:149: error: class, interface, or enum expected
            for (int i = r / B * B; i <= r; i++)
            ^
Main.java:149: error: class, interface, or enum expected
            for (int i = r / B * B; i <= r; i++)
                                    ^
Main.java:149: error: class, interface, or enum expected
            for (int i = r / B * B; i <= r; i++)
                                            ^
Main.java:151: error: class, interface, or enum expected
            for (int i = l / B + 1; i < r / B; i++)
            ^
Main.java:151: error: class, interface, or enum expected
            for (int i = l / B + 1; i < r / B; i++)
                                    ^
Main.java:151: error: class, interface, or enum expected
            for (int i = l / B + 1; i < r / B; i++)
                                               ^
Main.java:153: error: class, interface, or enum expected
        }
        ^
Main.java:156: error: class, interface, or enum expected
            for (int i = l / B + 1; i <= r / B; i++)
                                    ^
Main.java:156: error: class, interface, or enum expected
            for (int i = l / B + 1; i <= r / B; i++)
                                                ^
Main.java:158: error: class, interface, or enum expected
        }
        ^
Main.java:163: error: class, interface, or enum expected
        for (int i = l; i <= r; i++)
        ^
Main.java:163: error: class, interface, or enum expected
        for (int i = l; i <= r; i++)
                        ^
Main.java:163: error: class, interface, or enum expected
        for (int i = l; i <= r; i++)
                                ^
Main.java:165: error: class, interface, or enum expected
    }
    ^
Main.java:170: error: class, interface, or enum expected
};
^
Main.java:171: error: class, interface, or enum expected
void Yoshi()
^
Main.java:174: error: class, interface, or enum expected
    cin >> n >> q;
    ^
Main.java:175: error: class, interface, or enum expected
    vector<int> p(n);
    ^
Main.java:176: error: class, interface, or enum expected
    for (auto &i : p)
    ^
Main.java:178: error: class, interface, or enum expected
    pfs.resize(n + 1);
    ^
100 errors

Standard output is empty