Submission #963576

#	Time	Username	Problem	Language	Result	Execution time	Memory
963576		HoriaHaivas	Food Court (JOI21_foodcourt)	C++14	100 / 100	495 ms	107020 KiB

foodcourt

/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct query
{
    int type;
    int l;
    int r;
    int k;
    int c;
    int a;
    int b;
    int time;
    int ans;
};
int q;
vector<query> add[250005];
vector<query> rem[250005];
vector<query> answer[250005];
query qq[250005];

struct Node
{
    int minval;
    int lazy;
};
Node aint[1000005];

void prop(int val)
{
    if (aint[val].lazy==0)
        return;
    aint[val].minval+=aint[val].lazy;
    if (val*2+1<1000001)
    {
        aint[val*2].lazy+=aint[val].lazy;
        aint[val*2+1].lazy+=aint[val].lazy;
    }
    aint[val].lazy=0;
}

void lazy_update(int l, int r, int val, int qa, int qb, int x)
{
    prop(val);
    if (qa<=l && r<=qb)
    {
        aint[val].lazy+=x;
        return;
    }
    int mid;
    mid=(l+r)/2;
    if (qa<=mid)
    lazy_update(l,mid,val*2,qa,qb,x);
    if (qb>mid)
    lazy_update(mid+1,r,val*2+1,qa,qb,x);
    prop(val*2);
    prop(val*2+1);
    aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
}

int aint_query(int l, int r, int val, int qa, int qb)
{
    prop(val);
    if (qa<=l && r<=qb)
    {
        return aint[val].minval;
    }
    int mid,ans;
    mid=(l+r)/2;
    ans=1e18;
    if (qa<=mid)
    ans=min(ans,aint_query(l,mid,val*2,qa,qb));
    if (qb>mid)
    ans=min(ans,aint_query(mid+1,r,val*2+1,qa,qb));
    return ans;
}

int aib[250005];

void aib_update(int index, int delta)
{
    while (index<=q)
    {
        aib[index]+=delta;
        index+=index&(-index);
    }
}

int aib_query(int index)
{
    int ans=0;
    while (index>0)
    {
         ans+=aib[index];
         index-=index&(-index);
    }
    return ans;
}

int kth(int k)
{
    int r,pas;
    r=0;
    pas=(1<<18);
    while (pas)
    {
        if (r+pas<=q && aib_query(r+pas)<k)
            r+=pas;
        pas=pas/2;
    }
    return r+1;
}

signed main()
{
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,actually_left,actualb;
    cin >> n >> m >> q;
    for (i=1;i<=q;i++)
    {
         cin >> qq[i].type;
         qq[i].time=i;
         if (qq[i].type==1)
         {
             cin >> qq[i].l >> qq[i].r >> qq[i].c >> qq[i].k;
             add[qq[i].l].push_back(qq[i]);
             rem[qq[i].r+1].push_back(qq[i]);
         }
         else if (qq[i].type==2)
         {
             cin >> qq[i].l >> qq[i].r >> qq[i].k;
             add[qq[i].l].push_back(qq[i]);
             rem[qq[i].r+1].push_back(qq[i]);
         }
         else if (qq[i].type==3)
         {
             cin >> qq[i].a >> qq[i].b;
             answer[qq[i].a].push_back(qq[i]);
         }
    }
    for (i=1;i<=n;i++)
    {
         for (auto x : rem[i])
         {
              if (x.type==1)
              {
                  aib_update(x.time,-x.k);
                  lazy_update(1,q,1,x.time,q,-x.k);
              }
              else
              {
                  lazy_update(1,q,1,x.time,q,x.k);
              }
         }
         for (auto x : add[i])
         {
              if (x.type==1)
              {
                  aib_update(x.time,x.k);
                  lazy_update(1,q,1,x.time,q,x.k);
              }
              else
              {
                  lazy_update(1,q,1,x.time,q,-x.k);
              }
         }
         for (auto x : answer[i])
         {
              actually_left=aib_query(x.time)-(aint_query(1,q,1,x.time,x.time)-min(1LL*0,aint_query(1,q,1,1,x.time)));
              actualb=x.b+actually_left;
              if (kth(actualb)<=x.time)
              qq[x.time].ans=qq[kth(actualb)].c;
              else
              qq[x.time].ans=0;
         }
    }
    for (i=1;i<=q;i++)
    {
         if (qq[i].type==3)
         {
             cout << qq[i].ans << "\n";
         }
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:131:15: warning: unused variable 'j' [-Wunused-variable]
  131 |     int n,m,i,j,actually_left,actualb;
      |               ^

• 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