oj.uz

Submission #760803

# Submission time Handle Problem Language Result Execution time Memory
760803 2023-06-18T13:32:48 Z fuad27 Distributing Candies (IOI21_candies) C++17
100 / 100
 1386 ms 54264 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const int N_=200'010;
const long long INF=1e18;
struct node {
  long long mn=0, mx=0;
  int idn, idx;
  node(){}
  node(int at) {
    idn=idx=at;
  }
  node operator+(node B) {
   node res=(*this);
   if(res.mn>B.mn) {
    res.idn=B.idn;
   }
   if(res.mx<B.mx)res.idx=B.idx;
   res.mn=min(res.mn, B.mn);
   res.mx=max(res.mx, B.mx);
   return res;
  }
};
struct F1 {
  long long add=0;
  F1(){}
  node applyAggregate(node res) {
    res.mn+=add;
    res.mx+=add;
    return res;
  }
  void compose(F1 par) {
    add+=par.add;
  }
};
template<typename T, typename F>
struct ST {
  vector<T> t;
  vector<F> lz;
  T def;
  int n;
  ST(){}
  ST(int N) {
    n=N;
    t=vector<T>(4*n);
    lz=vector<F>(4*n);
  }
  void build(int tl, int tr, int v) {
    lz[v]=F();
    if(tl==tr) {
      t[v]=node(tl);
      return;
    }
    int tm=(tl+tr)/2;
    build(tl,tm,2*v);
    build(tm+1,tr,2*v+1);
    t[v]=t[2*v]+t[2*v+1];
  }
  void push(int v) {
    lz[2*v].compose(lz[v]);
    lz[2*v+1].compose(lz[v]);
    t[v]=lz[v].applyAggregate(t[v]);
    lz[v]=F();
  }
  T query(int l, int r, int tl, int tr, int v) {
    if(l>tr or r<tl)return def;
    if(l<=tl and tr<=r)return lz[v].applyAggregate(t[v]);
    push(v);
    int tm=(tl+tr)/2;
    return query(l,r,tl,tm,2*v)+query(l,r,tm+1,tr,2*v+1);
  }
  void update(int l, int r, F upd, int tl, int tr, int v) {
    if(r<tl or tr<l)return;
    if(l<=tl and tr<=r) {
      lz[v].compose(upd);
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    update(l,r,upd,tl,tm,2*v);
    update(l,r,upd,tm+1,tr,2*v+1);
    t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
  }
  void update(int at, T val, int tl, int tr, int v) {
    if(tl==tr) {
      t[v]=val;
      lz[v]=F();
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    if(at<=tm)update(at,val,tl,tm,2*v);
    else update(at,val,tm+1,tr,2*v+1);
    t[v]=lz[2*v].applyAggregate(t[2*v])+lz[2*v+1].applyAggregate(t[2*v+1]);
  }
  T query(int l, int r){return query(l,r,0,n-1,1);}
  void update(int l, int r, F upd){update(l,r,upd,0,n-1,1);}
  void update(int at, T val){update(at,val,0,n-1,1);}
  void build(){build(0,n-1,1);}
};
vector<int32_t> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n=c.size(), q=l.size();
  ST<node, F1> st(q+2);
  st.def.mx=-INF;
  st.def.mn=INF;
  st.build();
  vector<int32_t> res(n);
  vector<pair<int,long long>> ad[n+1];
  for(int i=0;i<q;i++) {
    ad[l[i]].push_back({i+2,v[i]});
    ad[r[i]+1].push_back({i+2,-v[i]});
  }
  for(int i = 0;i<n;i++) {
    {
      node tmp;
      tmp.mx=tmp.mn=c[i];
      st.update(0,tmp);
    }
    for(auto to:ad[i]) {
      F1 lz;
      lz.add=to.second;
      st.update(to.first, q+1, lz);
    }
    int lo=0, hi=q, ress=-1;
    while(lo <= hi) {
      int mid=(lo+hi)/2;
      node rs=st.query(mid,q+1);
      if(rs.mx-rs.mn>c[i]) {
        ress=mid;
        lo=mid+1;
      }
      else {
        hi=mid-1;
      }
    }
    if(ress==-1) {
      res[i]=st.query(q+1,q+1).mx;
      continue;
    }
    node rs=st.query(ress, q+1);
    if(rs.idn>rs.idx) {
      long long val=rs.mn;
      res[i]=st.query(q+1,q+1).mx-val;
    }
    else if(rs.idn<rs.idx){
      long long val=rs.mx;
      res[i]=st.query(q+1,q+1).mx-val+c[i];
    }
  }
  return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 6 ms 696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1282 ms 47552 KB Output is correct
2 Correct 1386 ms 51640 KB Output is correct
3 Correct 1309 ms 51540 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 223 ms 41992 KB Output is correct
3 Correct 387 ms 10860 KB Output is correct
4 Correct 1300 ms 53592 KB Output is correct
5 Correct 1331 ms 53876 KB Output is correct
6 Correct 1263 ms 54264 KB Output is correct
7 Correct 1214 ms 53724 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 119 ms 39164 KB Output is correct
4 Correct 363 ms 8864 KB Output is correct
5 Correct 1092 ms 47108 KB Output is correct
6 Correct 1096 ms 47780 KB Output is correct
7 Correct 1138 ms 48360 KB Output is correct
8 Correct 1099 ms 47008 KB Output is correct
9 Correct 1208 ms 48488 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 6 ms 696 KB Output is correct
6 Correct 1282 ms 47552 KB Output is correct
7 Correct 1386 ms 51640 KB Output is correct
8 Correct 1309 ms 51540 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 223 ms 41992 KB Output is correct
11 Correct 387 ms 10860 KB Output is correct
12 Correct 1300 ms 53592 KB Output is correct
13 Correct 1331 ms 53876 KB Output is correct
14 Correct 1263 ms 54264 KB Output is correct
15 Correct 1214 ms 53724 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 119 ms 39164 KB Output is correct
19 Correct 363 ms 8864 KB Output is correct
20 Correct 1092 ms 47108 KB Output is correct
21 Correct 1096 ms 47780 KB Output is correct
22 Correct 1138 ms 48360 KB Output is correct
23 Correct 1099 ms 47008 KB Output is correct
24 Correct 1208 ms 48488 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 353 ms 8916 KB Output is correct
27 Correct 215 ms 41548 KB Output is correct
28 Correct 1328 ms 52132 KB Output is correct
29 Correct 1287 ms 52584 KB Output is correct
30 Correct 1271 ms 52680 KB Output is correct
31 Correct 1339 ms 52880 KB Output is correct
32 Correct 1261 ms 53084 KB Output is correct