oj.uz

Submission #1044289

# Submission time Handle Problem Language Result Execution time Memory
1044289 2024-08-05T08:38:43 Z Unforgettablepl Distributing Candies (IOI21_candies) C++17
29 / 100
 1771 ms 1550160 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

pair<bool,int> combine(pair<bool,int> a,pair<bool,int> b){
    if(b.first)return b;
    return {a.first,a.second+b.second};
}

struct node{
    node *left, *right;
    int L,R;
    pair<bool,int> lazy;
    node(int L,int R):L(L),R(R),lazy(true,0),left(nullptr),right(nullptr){}
};

void update(int L,int R,node *curr,pair<bool,int> x){
    if(curr->R<L or R<curr->L)return;
    if(L<=curr->L and curr->R<=R){
        curr->lazy = combine(curr->lazy,x);
        return;
    }
    int mid = (curr->L + curr->R)/2;
    if(curr->left==nullptr)curr->left = new node(curr->L,mid);
    if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
    if(curr->lazy.first or curr->lazy.second){
        curr->left->lazy = combine(curr->left->lazy,curr->lazy);
        curr->right->lazy = combine(curr->right->lazy,curr->lazy);
        curr->lazy = {false,0};
    }
    update(L,R,curr->left,x);
    update(L,R,curr->right,x);
}

int getval(int x,node* curr){
    if(curr->L==curr->R){
        assert(curr->lazy.first);
        if(curr->lazy.second<0)return x+curr->lazy.second+1;
        else return curr->lazy.second;
    }
    int mid = (curr->L + curr->R)/2;
    if(curr->left==nullptr)curr->left = new node(curr->L,mid);
    if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
    if(curr->lazy.first or curr->lazy.second){
        curr->left->lazy = combine(curr->left->lazy,curr->lazy);
        curr->right->lazy = combine(curr->right->lazy,curr->lazy);
        curr->lazy = {false,0};
    }
    if(x<=mid)return getval(x,curr->left);
    else return getval(x,curr->right);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v){
    int n = c.size();
    int q = v.size();
    vector<int> s(n);
    node *head = new node(1,1e9);
    for(int i=0;i<q;i++){
        if(v[i]>0){
            int x = 0;
            for(int jump=536870912;jump;jump/=2){
                if(x+jump>1e9)continue;
                if(getval(x+jump,head)+v[i]>=x+jump)x+=jump;
            }
            if(x)update(1,x,head,{true,-1});
            update(x+1,1e9,head,{false,v[i]});
        } else {
            int x = 0;
            for(int jump=536870912;jump;jump/=2){
                if(x+jump>1e9)continue;
                if(getval(x+jump,head)+v[i]<=0)x+=jump;
            }
            if(x)update(1,x,head,{true,0});
            update(x+1,1e9,head,{false,v[i]});
        }
    }
    for(int i=0;i<n;i++)s[i]=getval(c[i],head);
    return s;
}

Compilation message

candies.cpp: In constructor 'node::node(int, int)':
candies.cpp:13:20: warning: 'node::lazy' will be initialized after [-Wreorder]
   13 |     pair<bool,int> lazy;
      |                    ^~~~
candies.cpp:11:11: warning:   'node* node::left' [-Wreorder]
   11 |     node *left, *right;
      |           ^~~~
candies.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     node(int L,int R):L(L),R(R),lazy(true,0),left(nullptr),right(nullptr){}
      |     ^~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 964 ms 116232 KB Output is correct
4 Correct 148 ms 96452 KB Output is correct
5 Correct 871 ms 49236 KB Output is correct
6 Correct 1141 ms 191360 KB Output is correct
7 Correct 1771 ms 1152224 KB Output is correct
8 Correct 909 ms 51800 KB Output is correct
9 Correct 1631 ms 1550160 KB Output is correct

Subtask #5
0 / 33.0

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