oj.uz

답안 #976836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
976836 2024-05-07T07:25:30 Z modwwe 푸드 코트 (JOI21_foodcourt) C++17
20 / 100
 282 ms 47824 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void ngha();
const int mod2=1e9+7;
const int  mod1=998244353;
struct ib
{
    int a;
    int b;
};
struct icd
{
    int a,b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
//#ifndef ONLINE_JUDGE
    /// fin(task),fou(task);
//#endif
    NHP
//modwwe
    //  cin>>res;
    ngha();

}
int c[250001];
ic t[1000001];
id b[250001];
void ff(int x)
{
     for(int i=x*2;i<=x*2+1;i++)
 {
    if(t[i].a>=t[x].b)t[i].a-=t[x].b;
        else t[i].a=0,t[i].b+=t[x].b-t[i].a;
    t[i].a+=t[x].a;
    t[i].c+=t[x].c;
 }
 t[x].a=t[x].b=t[x].c=0;
}
void upd(int node,int l,int r,int l1,int r1,int k,int z)
 {
     if(l>r1||r<l1) return;
     if(l>=l1&&r<=r1)
     { if(k==1)
         t[node].a+=z,t[node].c+=z;
       if(k==0)
       {
           if(t[node].a>=z)t[node].a-=z;
           else t[node].b+=z-t[node].a,t[node].a=0;
       }
      return;
     }
     ff(node);
     int mid=l+r>>1;
      upd(node<<1,l,mid,l1,r1,k,z);
      upd(node<<1|1,mid+1,r,l1,r1,k,z);
 }
 int get(int node,int l,int r,int l1,int r1)
 {
      if(l>r1||r<l1) return 0;
       if(l>=l1&&r<=r1) return t[node].a;
        int mid=l+r>>1;
         ff(node);
          return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
 }
 int get2(int node,int l,int r,int l1,int r1)
 {
      if(l>r1||r<l1) return 0;
       if(l>=l1&&r<=r1) return t[node].c;
       int mid=l+r>>1;
        ff(node);
        return get2(node<<1,l,mid,l1,r1)+get2(node<<1|1,mid+1,r,l1,r1);
 }
 int bit[250001];
 void upd(int x,int y)
 {
     for(x;x<=k;x+=x&-x)
        bit[x]+=y;
 }
 int get(int x)
 { int ss=0;
      for(x;x;x-=x&-x)
  ss+=bit[x];
  return ss;
 }
 vector<ib> v[250001];
 vector<ib> v2[250002];
vector<ib> v3[250002];
void ngha()
{
     cin>>n>>m>>k;
     for(int i=1;i<=k;i++)
     {
          cin>>l;
          if(l==3){cin>>l>>r;
          c[++dem]=0;
 s2=get2(1,1,n,l,l);
 s3=get(1,1,n,l,l);
 ///cout<<s2-s3+r<<" "<<l<<" "<<r<<" "<<s3,down
  if(r<=s3)
  { ///cout<<s2-s3+r<<" "<<s3,down
    v[l].pb({s2-s3+r,dem});
  }
             }
           else
           if(l==2)
           {
                cin>>l>>r>>s3;
                upd(1,1,n,l,r,0,s3);
           }
           else
            if(l==1)
           {
                cin>>l>>r>>s2>>s3;
                b[++dem2]={l,r,s2,s3};
                upd(1,1,n,l,r,1,s3);
                ///if(i==1)
             ///   cout<<get(1,1,n,3,3),down
           }
     }
     for(int i=1;i<=dem2;i++)
     {
  v2[b[i].a].pb({b[i].d,i});
     v3[b[i].b+1].pb({b[i].d,i});
     }
     for(int i=1;i<=n;i++)
     {
          for(auto x:v2[i])
          {
           upd(x.b,x.a);
          }
          for(auto x:v3[i])
          {
              upd(x.b,-x.a);
          }
          for(auto x:v[i])
          {
              l=1;
              r=k;
               while(l<=r)
               {
                   int mid=l+r>>1;
                   if(get(mid)>=x.a)r=mid-1;
                   else l=mid+1;
               }
             ///  cout<<r+1<<" "<<dem2<<" "<<get(3),down
               c[x.b]=b[r+1].c;
          }
     }
     for(int i=1;i<=dem;i++)
        cout<<c[i],down
}

Compilation message

foodcourt.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
foodcourt.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |      int mid=l+r>>1;
      |              ~^~
foodcourt.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid=l+r>>1;
      |                 ~^~
foodcourt.cpp: In function 'long long int get2(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |        int mid=l+r>>1;
      |                ~^~
foodcourt.cpp: In function 'void upd(long long int, long long int)':
foodcourt.cpp:107:10: warning: statement has no effect [-Wunused-value]
  107 |      for(x;x<=k;x+=x&-x)
      |          ^
foodcourt.cpp: In function 'long long int get(long long int)':
foodcourt.cpp:112:11: warning: statement has no effect [-Wunused-value]
  112 |       for(x;x;x-=x&-x)
      |           ^
foodcourt.cpp: In function 'void ngha()':
foodcourt.cpp:172:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |                    int mid=l+r>>1;
      |                            ~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 28808 KB Output is correct
2 Correct 51 ms 29368 KB Output is correct
3 Correct 64 ms 28752 KB Output is correct
4 Correct 55 ms 28556 KB Output is correct
5 Correct 52 ms 29268 KB Output is correct
6 Correct 54 ms 29524 KB Output is correct
7 Correct 20 ms 24984 KB Output is correct
8 Correct 21 ms 25048 KB Output is correct
9 Correct 51 ms 28960 KB Output is correct
10 Correct 50 ms 28952 KB Output is correct
11 Correct 50 ms 28956 KB Output is correct
12 Correct 49 ms 28756 KB Output is correct
13 Correct 48 ms 29012 KB Output is correct
14 Correct 53 ms 29520 KB Output is correct
15 Correct 51 ms 32408 KB Output is correct
16 Correct 53 ms 32344 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 30032 KB Output is correct
2 Correct 68 ms 30284 KB Output is correct
3 Correct 64 ms 30360 KB Output is correct
4 Correct 50 ms 29264 KB Output is correct
5 Correct 58 ms 29876 KB Output is correct
6 Correct 64 ms 30292 KB Output is correct
7 Correct 26 ms 28124 KB Output is correct
8 Correct 25 ms 25812 KB Output is correct
9 Correct 59 ms 30304 KB Output is correct
10 Correct 41 ms 29084 KB Output is correct
11 Correct 58 ms 30036 KB Output is correct
12 Correct 60 ms 30036 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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