Submission #106612

#	Time	Username	Problem	Language	Result	Execution time	Memory
106612		Alexa2001	Two Dishes (JOI19_dishes)	C++17	100 / 100	8368 ms	272076 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 1e6 + 5;
const ll inf = 1e18;


struct restrictie
{
    int x, y, add;
};
vector<restrictie> R[Nmax];

int n, m;

namespace rd
{
    const int bsize = 1<<16;
    char buffer[bsize+2];
    int cursor;

    static void refresh()
    {
        fread(buffer, 1, bsize, stdin), cursor = 0;
    }

    template <typename T>
    static void read(T &x)
    {
        x = 0;
        bool sgn = 0;
        while(!isdigit(buffer[cursor]))
        {
            sgn |= (buffer[cursor] == '-');
            ++cursor;
            if(cursor == bsize) refresh();
        }
        while(isdigit(buffer[cursor]))
        {
            x = x * 10 + buffer[cursor] - '0';
            ++cursor;
            if(cursor == bsize) refresh();
        }
        if(sgn) x *= (-1);
    }
}


void read_and_init()
{
    rd :: refresh();
    rd :: read(n); rd :: read(m);

    int i;
    vector<ll> A(n+1), B(m+1), S(n+1), T(m+1);
    vector<int> P(n+1), Q(m+1), T1(n+1), T2(m+1);

    for(i=1; i<=n; ++i) rd :: read(A[i]), rd :: read(S[i]), rd :: read(P[i]);
    for(i=1; i<=m; ++i) rd :: read(B[i]), rd :: read(T[i]), rd :: read(Q[i]);

    for(i=1; i<=n; ++i) A[i] += A[i-1];
    for(i=1; i<=m; ++i) B[i] += B[i-1];

    for(i=1; i<=n; ++i)
        T1[i] = upper_bound(B.begin(), B.end(), S[i] - A[i]) - B.begin() - 1;

    for(i=1; i<=m; ++i)
        T2[i] = upper_bound(A.begin(), A.end(), T[i] - B[i]) - A.begin() - 1;

    for(i=1; i<=n; ++i)
        R[i].push_back({ 0, T1[i], P[i] });

    for(i=1; i<=m; ++i)
        R[T2[i]+1].push_back({ i, m, Q[i] });
}



#define left_son ((node<<1))
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

namespace aint
{
    static ll mx[Nmax<<2], mn[Nmax<<2], val[Nmax<<2], add[Nmax<<2];
    static vector<int> split;

    static void propag(int node)
    {
        if(val[node] != inf)
        {
            mx[left_son] = mn[left_son] = mx[right_son] = mn[right_son] = val[node];
            val[left_son] = val[right_son] = val[node];

            val[node] = inf;
            add[left_son] = add[right_son] = 0;
        }

        if(add[node])
        {
            mx[left_son] += add[node];
            mn[left_son] += add[node];

            mx[right_son] += add[node];
            mn[right_son] += add[node];

            add[left_son] += add[node];
            add[right_son] += add[node];

            add[node] = 0;
        }
    }

    static void refresh(int node)
    {
        mx[node] = max(mx[left_son], mx[right_son]);
        mn[node] = min(mn[left_son], mn[right_son]);
    }

    static ll query(int node, int st, int dr, int pos)
    {
        if(st == dr) return mx[node];
        propag(node);

        if(pos <= mid) return query(left_son, st, mid, pos);
            else return query(right_son, mid+1, dr, pos);
    }

    static void Maxim(int node, int st, int dr, int Left, int Right, ll x)
    {
        if(Left <= st && dr <= Right)
        {
            if(mn[node] >= x) return;

            if(mx[node] <= x)
            {
                mx[node] = mn[node] = x;
                val[node] = x;
                add[node] = 0;
                return;
            }

            propag(node);

            Maxim(left_son, st, mid, Left, Right, x);
            Maxim(right_son, mid+1, dr, Left, Right, x);

            refresh(node);
            return;
        }

        propag(node);

        if(Left <= mid) Maxim(left_son, st, mid, Left, Right, x);
        if(mid < Right) Maxim(right_son, mid+1, dr, Left, Right, x);

        refresh(node);
    }

    void Add(int node, int st, int dr, int Left, int Right, ll delta)
    {
        if(Left <= st && dr <= Right)
        {
            add[node] += delta;
            mx[node] += delta;
            mn[node] += delta;
            return;
        }

        propag(node);

        if(Left <= mid) Add(left_son, st, mid, Left, Right, delta);
        if(mid < Right) Add(right_son, mid+1, dr, Left, Right, delta);

        refresh(node);
    }

    static void maximize()
    {
        int i;
        ll M = -inf;

        for(i=1; i<split.size()-1; ++i)
        {
            M = max(M, query(1, 0, m, split[i] - 1));
            Maxim(1, 0, m, split[i], split[i+1]-1, M);
        }
    }

    static void update(vector<restrictie> &v)
    {
        split.clear();
        split.push_back(0);
        split.push_back(m+1);

        for(auto &it : v)
            if(it.x <= it.y)
            {
                split.push_back(it.x);
                split.push_back(it.y+1);
            }

        sort(split.begin(), split.end());
        split.erase( unique(split.begin(), split.end()), split.end() );

        vector<ll> s(split.size(), 0);

        for(auto &it : v)
            if(it.x <= it.y)
            {
                s[lower_bound(split.begin(), split.end(), it.x) - split.begin()] += it.add;
                s[upper_bound(split.begin(), split.end(), it.y) - split.begin()] -= it.add;
            }

        ll sum = 0;
        int i;

        for(i=0; i<split.size()-1; ++i)
        {
            sum += s[i];
            Add(1, 0, m, split[i], split[i+1]-1, sum);
        }
    }

    static void init()
    {
        int i;
        for(i=1; i<=4*(m+1); ++i)
            add[i] = 0, mx[i] = mn[i] = 0, val[i] = inf;

        split.push_back(0);
        split.push_back(m+1);
    }

    static ll query(int pos)
    {
        return query(1, 0, m, pos);
    }
}

void solve()
{
    aint :: init();

    int i;
    for(i=1; i<=n+1; ++i)
    {
        aint :: maximize();
        aint :: update(R[i]);

     //   for(int j=0; j<=m; ++j)
      //      cerr << aint :: query(j) << ' ';
       // cerr << '\n';
    }

    cout << aint :: query(m) << '\n';
}

int main()
{
  //  freopen("input", "r", stdin);

    read_and_init();
    solve();

    return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'void aint::maximize()':
dishes.cpp:186:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<split.size()-1; ++i)
                  ~^~~~~~~~~~~~~~~
dishes.cpp: In function 'void aint::update(std::vector<restrictie>&)':
dishes.cpp:221:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<split.size()-1; ++i)
                  ~^~~~~~~~~~~~~~~
dishes.cpp: In function 'void rd::refresh()':
dishes.cpp:27:39: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buffer, 1, bsize, stdin), cursor = 0;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9