oj.uz

답안 #170667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170667 2019-12-26T02:52:19 Z puppies_and_rainbows Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 182944 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf=100000000000000000;
int it[4100000];
pair<int, int> lazy[4100000];

pair<int, int> merge(pair<int, int> u, pair<int, int> v)
{
    return {u.first+v.first, max(u.second, v.second+u.first)};
}

void down(int id, int l, int r)
{
    it[id]=max(it[id]+lazy[id].first, lazy[id].second);
    if(true)
    {
        lazy[id*2]=merge(lazy[id], lazy[id*2]);
        lazy[id*2+1]=merge(lazy[id], lazy[id*2+1]);
    }
    lazy[id]={0, -inf};
}

void update(int id, int l, int r, int u, int v, pair<int, int> val)
{
    down(id, l, r);
    if(l>v||r<u)
    {
        return;
    }
    if(l>=u&&r<=v)
    {
        lazy[id]=val;
        down(id, l, r);
        return;
    }
    int mid=(l+r)/2;
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    it[id]=max(it[id*2], it[id*2+1]);
}

int get(int id, int l, int r, int pos)
{
    down(id, l, r);
    if(l==r) return it[id];
    int mid=(l+r)/2;
    if(pos<=mid) return get(id*2, l, mid, pos);
    else return get(id*2+1, mid+1, r, pos);
}

int a[1000005], s[1000005], p[1000005];
int b[1000005], t[1000005], q[1000005];
int n, m;
vector<pair<int, int> > events[1000005];
signed main()
{
    //update(1,0,5,1,5,{1,0});
    //update(1,0,5,1,5,{1,0});
    //cout<<get(1,0,5,4);
    //return 0;
    //freopen("dishes.inp", "r", stdin);
    //freopen("dishes.out", "w", stdout);
    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];
    }
    int dora=0;
    for(int i=1; i<=n; i++)
    {
        int ok=upper_bound(b, b+m+1, s[i]-a[i])-b;
        if(ok>=1)
        {
            events[ok-1].push_back({i, p[i]});
        }
    }
    for(int i=1; i<=m; i++)
    {
        dora+=q[i]; q[i]=-q[i];
        int ok=upper_bound(a, a+n+1, t[i]-b[i])-a;
        if(ok<=n)
        {
            events[i-1].push_back({ok, q[i]});
        }
    }
    fill(lazy, lazy+n*4+5, (pair<int, int>){0, -inf});
    for(int p=0; p<m; p++)
    {
        for(auto i:events[p])
        {
            cout<<i.first<<" "<<i.second<<endl;
            update(1, 0, n, i.first, n, {i.second, -inf});
        }
        for(auto i:events[p])
        {
            if(i.first)
            {
                cout<<get(1, 0, n, i.first)<<endl;
                update(1, 0, n, i.first, n, {0, get(1, 0, n, i.first)});
            }
        }
        for(int i=0; i<=n; i++)
        {
            cout<<get(1, 0, n, i)<<" ";
        }
        cout<<endl;
    }
    for(auto i:events[m])
    {
        update(1, 0, n, i.first, n, {i.second, -inf});
    }
    cout<<dora-get(1, 0, n, n);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10012 ms 182944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10012 ms 182944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10012 ms 182944 KB Time limit exceeded
2 Halted 0 ms 0 KB -