oj.uz

Submission #157339

# Submission time Handle Problem Language Result Execution time Memory
157339 2019-10-11T00:13:12 Z combi1k1 Two Dishes (JOI19_dishes) C++14
0 / 100
 408 ms 95352 KB 
#include<bits/stdc++.h>

using namespace std;

#define X       first
#define Y       second
#define ll      long long
#define pb      push_back
#define lch     i << 1
#define rch     i << 1 | 1

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

typedef pair<ll,ll> ii;

ii  operator + (const ii &a,const ii &b)    {
    return  ii(a.X + b.X,max(a.Y + b.X,b.Y));
}

int n, m;
ll  res = 0;

ll  tr[N << 2];
ii  lz[N << 2];

int push(int i,int l,int r) {
    tr[i] = max(tr[i] + lz[i].X,lz[i].Y);
    if (l < r)  {
        lz[lch] = lz[lch] + lz[i];
        lz[rch] = lz[rch] + lz[i];
    }
    lz[i] = ii(0,-inf);
}
int _upd(int i,int l,int r,int L,int R,ii  v)   {
    push(i,l,r);
    if (R <  l || r <  L)   return  0;
    if (L <= l && r <= R)   {
        lz[i] = v;
        push(i,l,r);
        return  1;
    }
    int m = (l + r) / 2;
    _upd(lch,l,m,L,R,v);    ++m;
    _upd(rch,m,r,L,R,v);
    tr[i] = max(tr[lch],tr[rch]);
}
int _get(int i,int l,int r,int p)   {
    push(i,l,r);
    if (l == r) return  tr[i];
    int m = (l + r) / 2;
    if (p <= m) return  _get(lch,l,m,p);
    else    return ++m, _get(rch,m,r,p);
}

int a[N], s[N], p[N];
int b[N], t[N], q[N];

vector<ii>  v[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i = 1 ; i <= n ; ++i)   cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
    for(int i = 1 ; i <= m ; ++i)   cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];

    for(int i = 1 ; i <= n ; ++i)   {
        int x = upper_bound(b,b + 1 + m,s[i] - a[i]) - b;
        if (x >= 1) v[x - 1].pb({i,p[i]});
    }
    for(int i = 1 ; i <= m ; ++i)   {
        res  += q[i];
        q[i] = -q[i];
        int x = upper_bound(a,a + 1 + n,t[i] - b[i]) - a;
        if (x <= n) v[i - 1].pb({x,q[i]});
    }

    n++;
    fill(lz,lz + N * 4,ii(0,-inf));

    for(int i = 0 ; i < m ; ++i)    {
        for(ii  x : v[i])
            _upd(1,1,n,x.X + 1,n,{x.Y,-inf});
        for(ii  x : v[i])   if (x.X)
            _upd(1,1,n,x.X + 1,n,{0,_get(1,1,n,x.X)});
    }
    for(ii  x : v[m])   _upd(1,1,n,x.X + 1,n,{x.Y,-inf});

    cout << res + _get(1,1,n,n);
}

Compilation message

dishes.cpp: In function 'int push(int, int, int)':
dishes.cpp:34:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dishes.cpp: In function 'int _upd(int, int, int, int, int, ii)':
dishes.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 95352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 86520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 86520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 86520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 86520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 86520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 95352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 95352 KB Output isn't correct
2 Halted 0 ms 0 KB -