oj.uz

답안 #493306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493306 2021-12-10T20:56:35 Z gurkot 사탕 분배 (IOI21_candies) C++17
0 / 100
 1349 ms 62132 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "candies.h"
using namespace std;
const int nmax=200010,  qmin=0,  qmax=1;
const long long inf=1000000000000000LL;

struct Node {long long ma,mi,lazy; int ima,imi;};
Node tree[nmax*4];

void build(int u,int A,int B){ 
 if (A==B) {
   tree[u].ima=tree[u].imi=A;
   return;
 }
 int C=(A+B)/2;
 int left=u<<1; int right=left+1;
 build(left,A,C); build(right,C+1,B);
 tree[u].imi=tree[right].imi; 
 tree[u].ima=tree[right].ima;
}


void update(int u, int A, int B, int a, int b,long long val){	
 if (b<A || a>B) return;
 if (a<=A && B<=b) {
  tree[u].lazy+=val; return;
 }
 
 int C=(A+B)>>1;
 int left=u<<1; int right=left+1;
 if (tree[u].lazy!=0){
  tree[left].lazy+=tree[u].lazy;
  tree[right].lazy+=tree[u].lazy;
  tree[u].lazy=0;
 }
 update(left,A,C,a,b,val); update(right,C+1,B,a,b,val); 
 // change max
 if (tree[left].ma+tree[left].lazy  >
    tree[right].ma+tree[right].lazy){
    tree[u].ma=tree[left].ma+tree[left].lazy; 
	tree[u].ima=tree[left].ima;
 } else {
    tree[u].ma=tree[right].ma+tree[right].lazy; 
	tree[u].ima=tree[right].ima;
 }
 // change min 
 if (tree[left].mi+tree[left].lazy   <
    tree[right].mi+tree[right].lazy){
    tree[u].mi=tree[left].mi+tree[left].lazy; 
	tree[u].imi=tree[left].imi;
 } else {
    tree[u].mi=tree[right].mi+tree[right].lazy; 
	tree[u].imi=tree[right].imi;
 }
}

pair <long long, int> 
 getans(int u, int A, int B, int a, int b, int reg){
  if (b<A || a>B) {
   if (reg==qmax) return make_pair(-2*inf,-1);
             else return make_pair(2*inf,-1);
  }
  if (a<=A && B<=b) {
   if (reg==qmax)	
   return make_pair(tree[u].ma+tree[u].lazy,tree[u].ima);
   else
   return make_pair(tree[u].mi+tree[u].lazy,tree[u].imi);
  }
  
  int C=(A+B)>>1;
  int left=u<<1; int right=left+1;
  if (tree[u].lazy!=0){
   tree[left].lazy+=tree[u].lazy;
   tree[right].lazy+=tree[u].lazy;
   tree[u].lazy=0;
  }
  pair <long long, int> 
   maleft= getans(left,A,C,a,b,reg),
   maright=getans(right,C+1,B,a,b,reg);
   if (reg==qmax) {   
     if (maleft>maright) return maleft;
                    else return maright; 
   } else {
   	 if (maleft<maright) return maleft;
                    else return maright;
   }
}

vector <int> distribute_candies
 (vector<int>c, vector<int>l, vector<int>r, vector<int>v){

 int n=c.size(), q=l.size();
 vector <int> qon[n],qoff[n];
 vector <int> indon[n],indoff[n];
 vector <int> ans;
 
 build(1,0,q+1);
 update(1,0,q+1,0,q+1,-inf);  update(1,0,q+1,1,q+1,+inf);  
 
 for (int i=0;i<q;i++){
 	int x1=l[i], x2=r[i];
 	qon[x1].push_back(v[i]); qoff[x2].push_back(-v[i]);
 	indon[x1].push_back(i+2);  indoff[x2].push_back(i+2);
 }

 for (int i=0;i<n;i++){  
  int cnt=qon[i].size();
  for (int j=0;j<cnt;j++)
   update(1,0,q+1,indon[i][j],q+1,qon[i][j]);
   
  pair <long long, int> ma,mi;   
  long long res;  
 
   int A=0,B=q+1;    
   while (A<B){
  	int C=(A+B+1)/2; 
  	mi=getans(1,0,q+1,C,q+1,qmin);
  	ma=getans(1,0,q+1,C,q+1,qmax);
  	if (ma.first-mi.first>=(long long)c[i]) A=C; 
	                                   else B=C-1;
   }     
 
  mi=getans(1,0,q+1,A,q+1,qmin);  
  ma=getans(1,0,q+1,A,q+1,qmax);  
  res=getans(1,0,q+1,q+1,q+1,qmax).first;

  if (mi.second>ma.second) res=res-mi.first;
                      else res=c[i]-(ma.first-res);
           
  ans.push_back((int)res);
  cnt=qoff[i].size();
  for (int j=0;j<cnt;j++)
   update(1,0,q+1,indoff[i][j], q+1,qoff[i][j]);
 
 }//i
 return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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