제출 #493843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493843		gurkot	사탕 분배 (IOI21_candies)	C++17	40 / 100	1525 ms	59712 KiB

candies

#include <iostream>
#include <fstream>
#include <vector>
#include "candies.h"
using namespace std;
const int nmax=200110,  qmin=0,  qmax=1;
const long long inf=10000000000000LL;
int Q;
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)/2;
 int left=2*u; int right=left+1; 
 if (tree[u].lazy!=0){
  tree[left].lazy+=tree[u].lazy;
  tree[right].lazy+=tree[u].lazy;
  tree[u].mi+=tree[u].lazy; 
  tree[u].ma+=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)/2;
  int left=2*u; int right=left+1;
  if (tree[u].lazy!=0){
   tree[left].lazy+=tree[u].lazy;
   tree[right].lazy+=tree[u].lazy;
   tree[u].mi+=tree[u].lazy; 
   tree[u].ma+=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.first>maright.first) return maleft;
                                else return maright; 
   } else {
   	 if (maleft.first<maright.first) 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: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33