oj.uz

Submission #106610

# Submission time Handle Problem Language Result Execution time Memory
106610 2019-04-19T08:34:09 Z Alexa2001 Two Dishes (JOI19_dishes) C++17
0 / 100
 413 ms 74564 KB 
#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] = x;
                val[node] = x;
                add[node] = 0;
                return;
            }

            Maxim(left_son, st, mid, Left, Right, x);
            Maxim(right_son, mid+1, dr, Left, Right, x);
            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

dishes.cpp: In function 'void aint::maximize()':
dishes.cpp:182: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:217: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 58552 KB Output is correct
2 Correct 413 ms 61712 KB Output is correct
3 Correct 353 ms 74564 KB Output is correct
4 Correct 287 ms 70108 KB Output is correct
5 Correct 29 ms 23808 KB Output is correct
6 Incorrect 405 ms 73824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 30 ms 23808 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 26 ms 23808 KB Output is correct
8 Correct 24 ms 23808 KB Output is correct
9 Correct 26 ms 23928 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 27 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 30 ms 23808 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 26 ms 23808 KB Output is correct
8 Correct 24 ms 23808 KB Output is correct
9 Correct 26 ms 23928 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 27 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 30 ms 23808 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 26 ms 23808 KB Output is correct
8 Correct 24 ms 23808 KB Output is correct
9 Correct 26 ms 23928 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 27 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 30 ms 23808 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 26 ms 23808 KB Output is correct
8 Correct 24 ms 23808 KB Output is correct
9 Correct 26 ms 23928 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 27 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 30 ms 23808 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 26 ms 23808 KB Output is correct
8 Correct 24 ms 23808 KB Output is correct
9 Correct 26 ms 23928 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 27 ms 23800 KB Output is correct
13 Incorrect 28 ms 23928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 58552 KB Output is correct
2 Correct 413 ms 61712 KB Output is correct
3 Correct 353 ms 74564 KB Output is correct
4 Correct 287 ms 70108 KB Output is correct
5 Correct 29 ms 23808 KB Output is correct
6 Incorrect 405 ms 73824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 58552 KB Output is correct
2 Correct 413 ms 61712 KB Output is correct
3 Correct 353 ms 74564 KB Output is correct
4 Correct 287 ms 70108 KB Output is correct
5 Correct 29 ms 23808 KB Output is correct
6 Incorrect 405 ms 73824 KB Output isn't correct
7 Halted 0 ms 0 KB -