Submission #1033294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033294		alexdd	Food Court (JOI21_foodcourt)	C++17	100 / 100	685 ms	96584 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,q;
pair<pair<int,int>,pair<int,int>> aint[530000][3];
int lazy[530000][3];
pair<pair<int,int>,pair<int,int>> emp = {{INF,INF},{-INF,-INF}};
pair<pair<int,int>,pair<int,int>> combine(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
    return {min(x.first,y.first),max(x.second,y.second)};
}
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod][0] = aint[nod][1] = aint[nod][2] = {{0,st},{0,st}};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod][0] = combine(aint[nod*2][0], aint[nod*2+1][0]);
    aint[nod][1] = combine(aint[nod*2][1], aint[nod*2+1][1]);
    aint[nod][2] = combine(aint[nod*2][2], aint[nod*2+1][2]);
}
void propagate(int nod, int c)
{
    if(!lazy[nod][c])
        return;
    lazy[nod*2][c]+=lazy[nod][c];
    lazy[nod*2+1][c]+=lazy[nod][c];
    aint[nod*2][c].first.first+=lazy[nod][c];
    aint[nod*2][c].second.first+=lazy[nod][c];
    aint[nod*2+1][c].first.first+=lazy[nod][c];
    aint[nod*2+1][c].second.first+=lazy[nod][c];
    lazy[nod][c]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv, int c)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        lazy[nod][c]+=newv;
        aint[nod][c].first.first+=newv;
        aint[nod][c].second.first+=newv;
        return;
    }
    propagate(nod,c);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv,c);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv,c);
    aint[nod][c] = combine(aint[nod*2][c], aint[nod*2+1][c]);
}
pair<pair<int,int>,pair<int,int>> qry(int nod, int st, int dr, int le, int ri, int c)
{
    if(le>ri)
        return emp;
    if(le==st && dr==ri)
        return aint[nod][c];
    propagate(nod,c);
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri),c),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}
int cautare_binara(int nod, int st, int dr, int x)
{
    if(st==dr)
    {
        if(aint[nod][1].first.first>=x)
            return st;
        else
            return -1;
    }
    propagate(nod,1);
    int mij=(st+dr)/2;
    if(aint[nod*2][1].second.first>=x)
        return cautare_binara(nod*2,st,mij,x);
    else
        return cautare_binara(nod*2+1,mij+1,dr,x);
}
vector<pair<int,int>> upds[250005];
vector<pair<int,int>> qrys[250005];
int rez[250005];
int cit[250005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    int tip,le,ri,c,k,a,b;
    for(int i=1;i<=q;i++)
    {
        cin>>tip;
        rez[i] = -7;
        if(tip==1)
        {
            cin>>le>>ri>>c>>k;
            upds[le].push_back({i,k});
            upds[ri+1].push_back({i,-k});
            cit[i]=c;
        }
        else if(tip==2)
        {
            cin>>le>>ri>>k;
            upds[le].push_back({-i,k});
            upds[ri+1].push_back({-i,-k});
        }
        else
        {
            cin>>a>>b;
            qrys[a].push_back({b,i});
        }
    }
    build(1,0,q);
    for(int i=1;i<=n;i++)
    {
        for(auto [t,newv]:upds[i])
        {
            if(t < 0)
            {
                t = -t;
                upd(1,0,q,t,q,-newv,0);
                upd(1,0,q,t,q,newv,2);
            }
            else
            {
                upd(1,0,q,t,q,newv,0);
                upd(1,0,q,t,q,newv,1);
            }
        }
        for(auto [x,t]:qrys[i])
        {
            pair<pair<int,int>,pair<int,int>> aux = qry(1,0,q,0,t,0);
            int ult = aux.first.second;
            int scazute = qry(1,0,q,t,t,2).first.first - qry(1,0,q,ult,ult,2).first.first;
            int pref1 = qry(1,0,q,ult,ult,1).first.first;
            int ans = cautare_binara(1,0,q,x+pref1+scazute);
            if(ans==-1 || ans>t)
            {
                rez[t]=0;
            }
            else
            {
                rez[t]=cit[ans];
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(rez[i]==-7)
            continue;
        cout<<rez[i]<<"\n";
    }
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11