oj.uz

답안 #439897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439897 2021-07-01T06:57:53 Z loctildore 사탕 분배 (IOI21_candies) C++17
0 / 100
 1225 ms 47528 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
    os << '[';
    bool E = false;
    for(const T& x : a) {
        if(E) os << ' ';
        os << x;
        E = true;
    }
    return os << ']';
}
struct node{
  int l,r;
  node *lft = NULL,*rght = NULL;
  int offset = 0, minimum = 0, maximum = 0;
  //offset is already applied to min/max at this layer
  node(int ltemp, int rtemp){
    l=ltemp;r=rtemp;
  }
};
void add(node *x, int l, int r, int val) {
  if (r <= x->l||x->r <= l) {
    return;
  }
  if (l <= x->l&&x->r <= r) {
    x->offset+=val;
    x->minimum+=val;
    x->maximum+=val;
    return;
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  add(x->lft,l,r,val);
  add(x->rght,l,r,val);
  x->minimum=min(x->lft->minimum,x->rght->minimum)+x->offset;
  x->maximum=max(x->lft->maximum,x->rght->minimum)+x->offset;
}
int findval(node *x, int point){
  if (point < x->l||x->r <= point) {
    return INT_MIN;
  }
  if (x->l+1==x->r) {
    return x->offset;
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  int temp = findval(x->lft, point);
  if (temp == INT_MIN){
    temp = findval(x->rght, point);
  }
  return temp+x->offset;
}
pair<int,int> limitfind(node *x, int l, int r){
  if (r <= x->l||x->r <= l) {
    return {INT_MIN,INT_MAX};
  }
  if (l <= x->l&&x->r <= r) {
    return {x->maximum,x->minimum};
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  pair<int,int> tempa=limitfind(x->lft,l,r);
  pair<int,int> tempb=limitfind(x->rght,l,r);
  return {max(tempa.f,tempb.f)+x->offset,min(tempa.s,tempb.s)+x->offset};
}
node *root;
vector<int> strt[200069],nd[200069];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  root=new node(0,200069);
  vector<int> rtn;
  for (int i = 0; i < v.size(); i++) {
    strt[l[i]].push_back(i);
    nd[r[i]+1].push_back(i);
  }
  add(root,0,200069,1000000069);
  add(root,1,200069,-1000000069);
  for (int i = 0; i < c.size(); i++) {
    for (int j : strt[i]) {
      add(root,j+2,200069,v[j]);
    }
    for (int j : nd[i]) {
      add(root,j+2,200069,-v[j]);
    }
    int s=-1,e=200068;
    while (s+1!=e) {
      int m=e-(e-s)/2;
      pair<int,int> temp=limitfind(root, m, 200069);
      if (temp.f-temp.s<=c[i]){
        e=m;
      }
      else{
        s=m;
      }
    }
    int temp=findval(root, 200068)-findval(root, e);
    if (findval(root, e)-findval(root, e-1)>0) {
      temp+=c[i];
    }
    rtn.push_back(temp);
  }
  return rtn;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i = 0; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~
candies.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int i = 0; i < c.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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