oj.uz

Submission #623574

# Submission time Handle Problem Language Result Execution time Memory
623574 2022-08-06T02:03:53 Z ACGN Distributing Candies (IOI21_candies) C++17
29 / 100
 2367 ms 798436 KB 
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define pb push_back
#include "candies.h"
const int MAX = 1<<30;

struct Node {
    int val,lazy,l,r,sl,sr;
    Node(int lb,int rb) {
        val=0;lazy=-1;l=-1;r=-1;sl=lb;sr=rb;
    }
    Node() {
        val=0;lazy=-1;l=-1;r=-1;sl=0;sr=MAX;
    }
};

struct ilst {
    vector<Node> vn;
    int val = 0;
    ilst() {
        vn.pb(Node());
    }
    void push(int pos) {
        //cout<<"p("<<pos<<") ";
        int lh=vn[pos].sl;
        int rh=vn[pos].sr;
        int mh=(lh+rh)/2;
        if ((rh==lh+1)) {
            if (vn[pos].lazy!=-1) vn[pos].val=vn[pos].lazy;
            vn[pos].lazy=-1;return;
        }
        if (vn[pos].l==-1) {
            vn[pos].l=vn.size();
            vn.pb(Node(lh,mh));
        }
        if (vn[pos].r==-1) {
            vn[pos].r=vn.size();
            vn.pb(Node(mh,rh));
        }

        if (vn[pos].lazy==-1) return;
        //vn[pos].val=vn[pos].lazy * (rh-lh);
        vn[vn[pos].l].lazy = vn[pos].lazy; 
        vn[vn[pos].l].val  = vn[pos].lazy * (mh-lh);
        vn[vn[pos].r].lazy = vn[pos].lazy; 
        vn[vn[pos].r].val  = vn[pos].lazy * (mh-lh);
        vn[pos].lazy=-1;
    }
    int sum(int x) {
        //cout<<"sum("<<x<<")";
        int total = 0,cp=0;
        for (int i=29;i>=0;i--) {
            int dest;
            push(cp);
            if (x&(1<<i)) {
                dest=vn[cp].r;
                int lp = vn[cp].l;if (lp!=-1) {
                    //push(lp);
                    total+=vn[lp].val;
                }
                if (dest==-1) {return total;}
            }
            else {
                dest=vn[cp].l;
                if (dest==-1) {return total;}
            }
            cp=dest;
        }
        {return total;}
    }
    int _bs(int cp,int x) { // first t,sum(t)>=x
        int dest;
        if (vn[cp].sr==vn[cp].sl+1) return vn[cp].sr;
        push(cp);
        int v = vn[vn[cp].l].val;
        if (v>=x) return _bs(vn[cp].l,x);
        x-=v;return _bs(vn[cp].r,x);
    }
    int bs(int x) {
        if (vn[0].val<x) return MAX;
        return _bs(0,x);
    }
    void _upd(int i,int cl,int cr,int tl,int tr,int val) {
        if (i==-1) return;
        if (cr<=tl) return;
        if (tr<=cl) return;
        if ((tl<=cl)&&(cr<=tr)) {
            vn[i].val=val*(cr-cl);
            vn[i].lazy=val;return;
        }
        push(i);
        int mid = (cl+cr)/2;
        _upd(vn[i].l,cl,mid,tl,tr,val);
        _upd(vn[i].r,mid,cr,tl,tr,val);
        vn[i].val = vn[vn[i].l].val + vn[vn[i].r].val;
    }
    void upd(int l,int r,int v) {
        val = v;
        //cout<<"UPD("<<l<<","<<r<<","<<v<<")\n";
        _upd(0,0,MAX,l,r,v);
    }
};

vi distribute_candies(vi c,vi l,vi r,vi v) {
    int n = c.size();
    ilst st;
    //cout<<"HI?"<<endl;
    for (auto e:v) {
        if (e>0) {
            st.upd(0,1,st.val+e);
            //cout<<"OK UPD"<<endl;
            int lo=0,hi=MAX;
            while (hi>lo+1) {
                int mid = (hi+lo)/2;
                if (st.sum(mid)>mid) lo=mid;
                else hi=mid;
            }
            //cout<<hi<<endl;
            st.upd(0,hi,1);

            //cout<<"OK DONE"<<endl;
        }
        else {
            //cout<<st.bs(-e)<<endl;
            st.upd(0,st.bs(-e),0);

            //cout<<"OK UPD DONE"<<endl;
        }
    }
    vi va;
    for (int i=0;i<c.size();i++) {
        va.pb(st.sum(c[i]));
    }
    return va;
}

Compilation message

candies.cpp: In member function 'int ilst::_bs(int, int)':
candies.cpp:76:13: warning: unused variable 'dest' [-Wunused-variable]
   76 |         int dest;
      |             ^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i=0;i<c.size();i++) {
      |                  ~^~~~~~~~~
candies.cpp:109:9: warning: unused variable 'n' [-Wunused-variable]
  109 |     int n = c.size();
      |         ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2157 ms 204276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 930 ms 54852 KB Output is correct
4 Correct 170 ms 52100 KB Output is correct
5 Correct 804 ms 32984 KB Output is correct
6 Correct 1075 ms 106560 KB Output is correct
7 Correct 1639 ms 401940 KB Output is correct
8 Correct 793 ms 35000 KB Output is correct
9 Correct 2367 ms 798436 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -