oj.uz

Submission #106611

# Submission time Handle Problem Language Result Execution time Memory
106611 2019-04-19T08:36:56 Z Alexa2001 Two Dishes (JOI19_dishes) C++17
3 / 100
 407 ms 61180 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] = mn[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 364 ms 58160 KB Output is correct
2 Correct 343 ms 58192 KB Output is correct
3 Correct 240 ms 61180 KB Output is correct
4 Correct 271 ms 56424 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Incorrect 407 ms 57160 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 29 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 25 ms 23808 KB Output is correct
8 Correct 29 ms 23800 KB Output is correct
9 Correct 31 ms 23828 KB Output is correct
10 Correct 25 ms 23800 KB Output is correct
11 Correct 27 ms 23800 KB Output is correct
12 Correct 24 ms 23808 KB Output is correct
13 Correct 28 ms 23892 KB Output is correct
14 Correct 21 ms 23672 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 27 ms 23888 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 29 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 25 ms 23808 KB Output is correct
8 Correct 29 ms 23800 KB Output is correct
9 Correct 31 ms 23828 KB Output is correct
10 Correct 25 ms 23800 KB Output is correct
11 Correct 27 ms 23800 KB Output is correct
12 Correct 24 ms 23808 KB Output is correct
13 Correct 28 ms 23892 KB Output is correct
14 Correct 21 ms 23672 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 27 ms 23888 KB Output is correct
17 Correct 29 ms 24448 KB Output is correct
18 Correct 28 ms 24448 KB Output is correct
19 Incorrect 29 ms 24420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 29 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 25 ms 23808 KB Output is correct
8 Correct 29 ms 23800 KB Output is correct
9 Correct 31 ms 23828 KB Output is correct
10 Correct 25 ms 23800 KB Output is correct
11 Correct 27 ms 23800 KB Output is correct
12 Correct 24 ms 23808 KB Output is correct
13 Correct 28 ms 23892 KB Output is correct
14 Correct 21 ms 23672 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 27 ms 23888 KB Output is correct
17 Correct 29 ms 24448 KB Output is correct
18 Correct 28 ms 24448 KB Output is correct
19 Incorrect 29 ms 24420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 29 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 25 ms 23808 KB Output is correct
8 Correct 29 ms 23800 KB Output is correct
9 Correct 31 ms 23828 KB Output is correct
10 Correct 25 ms 23800 KB Output is correct
11 Correct 27 ms 23800 KB Output is correct
12 Correct 24 ms 23808 KB Output is correct
13 Correct 28 ms 23892 KB Output is correct
14 Correct 21 ms 23672 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 27 ms 23888 KB Output is correct
17 Correct 29 ms 24448 KB Output is correct
18 Correct 28 ms 24448 KB Output is correct
19 Incorrect 29 ms 24420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct
4 Correct 29 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 25 ms 23808 KB Output is correct
8 Correct 29 ms 23800 KB Output is correct
9 Correct 31 ms 23828 KB Output is correct
10 Correct 25 ms 23800 KB Output is correct
11 Correct 27 ms 23800 KB Output is correct
12 Correct 24 ms 23808 KB Output is correct
13 Correct 28 ms 23892 KB Output is correct
14 Correct 21 ms 23672 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 27 ms 23888 KB Output is correct
17 Correct 29 ms 24448 KB Output is correct
18 Correct 28 ms 24448 KB Output is correct
19 Incorrect 29 ms 24420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 58160 KB Output is correct
2 Correct 343 ms 58192 KB Output is correct
3 Correct 240 ms 61180 KB Output is correct
4 Correct 271 ms 56424 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Incorrect 407 ms 57160 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 58160 KB Output is correct
2 Correct 343 ms 58192 KB Output is correct
3 Correct 240 ms 61180 KB Output is correct
4 Correct 271 ms 56424 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Incorrect 407 ms 57160 KB Output isn't correct
7 Halted 0 ms 0 KB -