oj.uz

답안 #255615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255615 2020-08-01T12:38:55 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 3252 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
 
int n,q,k;
deque<lli> segt[400001];
int lazy[400001]={};
lli qu(lli node,lli l,lli r,lli s,lli e)
{
  if(r<s||l>e)
    return(0);
  if(lazy[node]!=0)
  {
    lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],51);
    lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],51);
    while(lazy[node]!=0)
    {
      if(k==1)
        segt[node].pb(segt[node].front());
      else
        segt[node].pb(0);
      segt[node].pop_front();
      lazy[node]-=1;
      if(segt[node].size()>51)
        exit(1);
    }
  }
  if(l>=s&&r<=e)
    return(segt[node].front());
  lli m=(l+r)/2;
  lli q1=qu(2*node+1,l,m,s,e),q2=qu(2*node+2,m+1,r,s,e);
  return(q1+q2);
}
void up2(lli node,lli l,lli r,lli s,lli e)
{
  if(l>e||r<s)
    return;
  if(lazy[node]!=0)
  {
    lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],51);
    lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],51);
    while(lazy[node]!=0)
    {
      if(k==1)
        segt[node].pb(segt[node].front());
      else
        segt[node].pb(0);
      segt[node].pop_front();
      lazy[node]-=1;
      if(segt[node].size()>51)
        exit(1);
    }
  }
  if(l>=s&&r<=e)
  {
    if(k==1)
        segt[node].pb(segt[node].front());
      else
        segt[node].pb(0);
    segt[node].pop_front();
    lazy[2*node+1]=min(lazy[2*node+1]+1,51);
    lazy[2*node+2]=min(lazy[2*node+2]+1,51);
    return;
  }
  lli m=(l+r)/2;
  up2(2*node+1,l,m,s,e);
  up2(2*node+2,m+1,r,s,e);
  segt[node].clear();
  qu(2*node+1,l,m,l,m);
  qu(2*node+2,m+1,r,m+1,r);
  while(segt[node].size()!=51)
  {
    segt[node].pb(segt[2*node+1].at(segt[node].size())+segt[2*node+2].at(segt[node].size()));
    if(segt[node].size()>51)
        exit(1);
  }
}
int c=0;
void up1(lli node,lli l,lli r,lli in,lli v)
{
  if(lazy[node]!=0)
  {
    lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],51);
    lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],51);
    while(lazy[node]!=0)
    {
      if(k==1)
        segt[node].pb(segt[node].front());
      else
        segt[node].pb(0);
      segt[node].pop_front();
      lazy[node]-=1;
      if(segt[node].size()>51)
        exit(1);
    }
  }
  if(l==r)
  {
    lazy[node]=0;
    segt[node].clear();
    while(segt[node].size()!=51)
    {
      segt[node].pb(v);
      v/=k;
      if(segt[node].size()>51)
        exit(1);
    }
    return;
  }
  lli m=(l+r)/2;
  if(in<=m)
    up1(2*node+1,l,m,in,v);
  else
    up1(2*node+2,m+1,r,in,v);
  segt[node].clear();
  qu(2*node+1,l,m,l,m);
  qu(2*node+2,m+1,r,m+1,r);
  while(segt[node].size()!=51)
  {
    segt[node].pb(segt[2*node+1].at(segt[node].size())+segt[2*node+2].at(segt[node].size()));
    if(segt[node].size()>51)
        exit(1);
  }
}
void init(lli node,lli l,lli r)
{
    while(segt[node].size()!=51)
    {
      segt[node].pb(0);
      if(segt[node].size()>51)
        exit(1);
    }
    lli m=(l+r)/2;
    if(l!=r)
    {
      init(2*node+1,l,m);
      init(2*node+2,m+1,r);
    }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>q>>k;
  init(0,0,n-1);
  for(lli i=0;i<n;++i)
  {
    lli f;
    cin>>f;
    up1(0,0,n-1,i,f);
  }
  for(lli i=0;i<q;++i)
  {
    lli f,s,t;
    cin>>f>>s>>t;
    if(f==1)
    {
      s--;
      up1(0,0,n-1,s,t);
    }
    else if(f==2)
    {
      s--;
      t--;
      up2(0,0,n-1,s,t);
    }
    else
    {
      s--;
      t--;
      cout<<qu(0,0,n-1,s,t)<<endl;
    }
    if(sizeof(segt)/4>400001*51)
      exit(1);
  }
  return(0);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 269820 KB Output is correct
2 Correct 224 ms 270200 KB Output is correct
3 Correct 257 ms 270072 KB Output is correct
4 Correct 240 ms 270840 KB Output is correct
5 Correct 304 ms 271992 KB Output is correct
6 Correct 262 ms 272248 KB Output is correct
7 Correct 274 ms 272120 KB Output is correct
8 Correct 257 ms 272120 KB Output is correct
9 Correct 259 ms 272120 KB Output is correct
10 Correct 306 ms 272120 KB Output is correct
11 Correct 266 ms 272164 KB Output is correct
12 Correct 260 ms 272096 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3252 ms 311900 KB Output is correct
2 Correct 2560 ms 299896 KB Output is correct
3 Runtime error 1243 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 851 ms 275576 KB Output is correct
2 Correct 1055 ms 299000 KB Output is correct
3 Correct 1261 ms 303468 KB Output is correct
4 Correct 2455 ms 291588 KB Output is correct
5 Runtime error 1529 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2401 ms 313764 KB Output is correct
2 Correct 2771 ms 314836 KB Output is correct
3 Correct 1935 ms 307976 KB Output is correct
4 Correct 2891 ms 297848 KB Output is correct
5 Runtime error 1547 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -