Submission #953013

#	Time	Username	Problem	Language	Result	Execution time	Memory
953013		groshi	Food Court (JOI21_foodcourt)	C++17	100 / 100	388 ms	77140 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define int long long
int drzewo[4000000][2];
int drzewo2[4000000];
int lazy[4000000];
int t[300000];
int l[300000];
int r[300000];
int c[300000];
int k[300000];
int a[300000];
int b[300000];
int wynik[300000];
int stala=250000;
vector<pair<int,int> > dodaaj[300000],usun[300000],essa[300000];
int pot=1;
void dodaj(int x,int co,int gdzie)
{
    x++;
    for(;x<=stala;x+=x&-x)
        drzewo[x][gdzie]+=co;
}
int zap(int x,int gdzie)
{
    x++;
    int wynik=0;
    for(;x;x&=(x-1))
        wynik+=drzewo[x][gdzie];
    return wynik;
}
int szukaj(int x,int gdziee)
{
    int gdzie=0;
    for(int i=19;i>=0;i--)
    {
        if((gdzie|(1<<i))<=stala && drzewo[(gdzie|(1<<i))][gdziee]<x)
        {
            gdzie|=(1<<i);
            x-=drzewo[gdzie][gdziee];
        }
    }
    return gdzie;
}
void propaguj(int x)
{
    drzewo2[x*2]+=lazy[x];
    drzewo2[x*2+1]+=lazy[x];
    lazy[x*2]+=lazy[x];
    lazy[x*2+1]+=lazy[x];
    lazy[x]=0;
}
void dodaj2(int x,int l,int r,int L,int R,int ile)
{
    if(R<l || L>r)
        return;
    if(L<=l && r<=R)
    {
        drzewo2[x]+=ile;
        lazy[x]+=ile;
        return;
    }
    propaguj(x);
    int mid=(l+r)/2;
    dodaj2(x*2,l,mid,L,R,ile);
    dodaj2(x*2+1,mid+1,r,L,R,ile);
    drzewo2[x]=min(drzewo2[x*2],drzewo2[x*2+1]);
}
int zap2(int x,int l,int r,int L,int R)
{
    if(R<l || L>r)
        return 0;
    if(L<=l && r<=R)
        return drzewo2[x];
    propaguj(x);
    int mid=(l+r)/2;
    int wynik=min(zap2(x*2,l,mid,L,R),zap2(x*2+1,mid+1,r,L,R));
    drzewo2[x]=min(drzewo2[x*2],drzewo2[x*2+1]);
    return wynik;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    while(pot<=q)
        pot*=2;
    pot--;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i];
        if(t[i]==1)
        {
            cin>>l[i]>>r[i]>>c[i]>>k[i];
            dodaaj[l[i]].push_back({i,k[i]});
            dodaaj[r[i]+1].push_back({i,-k[i]});
        }
        else if(t[i]==2)
        {
            cin>>l[i]>>r[i]>>k[i];
            usun[l[i]].push_back({i,k[i]});
            usun[r[i]+1].push_back({i,-k[i]});
        }
        else{
            cin>>a[i]>>b[i];
            essa[a[i]].push_back({i,b[i]});
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<usun[i].size();j++)
        {
            //cout<<"dodaje "<<usun[i][j].first<<" "<<-usun[i][j].second<<"\n";
            dodaj(usun[i][j].first,-usun[i][j].second,0);
            dodaj2(1,pot+1,q+pot,usun[i][j].first+pot,q+pot,-usun[i][j].second);
        }
        for(int j=0;j<dodaaj[i].size();j++)
        {
            //cout<<"dodaje 2 "<<dodaaj[i][j].first<<" "<<dodaaj[i][j].second<<"\n";
            dodaj(dodaaj[i][j].first,dodaaj[i][j].second,0);
            dodaj(dodaaj[i][j].first,dodaaj[i][j].second,1);
            dodaj2(1,pot+1,q+pot,dodaaj[i][j].first+pot,q+pot,dodaaj[i][j].second);
        }
        for(int j=0;j<essa[i].size();j++)
        {
            int gdzie=essa[i][j].first;
            int ile=essa[i][j].second;
            //cout<<ile<<"\n";
            //cout<<zap(gdzie,1)<<" "<<zap(gdzie,0)<<" "<<zap2(1,0,q,0,gdzie+1)<<"\n";
            ile+=zap(gdzie,1)-zap(gdzie,0)+min(zap2(1,pot+1,q+pot,pot+1,gdzie+pot),0LL);
            //cout<<"mam teraz "<<ile<<"\n";
            if(ile>zap(gdzie,1))
                wynik[gdzie]=-1;
            else wynik[gdzie]=szukaj(ile,1);
            //cout<<gdzie<<": "<<wynik[gdzie]<<"\n";
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(t[i]==3)
        {
            if(wynik[i]==-1)
                cout<<"0\n";
            else cout<<c[wynik[i]]<<"\n";
        }
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:113:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j=0;j<usun[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~
foodcourt.cpp:119:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j=0;j<dodaaj[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~
foodcourt.cpp:126:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int j=0;j<essa[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~

• 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