oj.uz

Submission #493844

# Submission time Handle Problem Language Result Execution time Memory
493844 2021-12-13T07:26:56 Z gurkot Distributing Candies (IOI21_candies) C++17
100 / 100
 1558 ms 59600 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include "candies.h"
using namespace std;
const int nmax=300110,  qmin=0,  qmax=1;
const long long inf=1000000000000000LL;
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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 6 ms 844 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1404 ms 57464 KB Output is correct
2 Correct 1488 ms 57316 KB Output is correct
3 Correct 1489 ms 57288 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 246 ms 26876 KB Output is correct
3 Correct 431 ms 23080 KB Output is correct
4 Correct 1558 ms 57320 KB Output is correct
5 Correct 1481 ms 57328 KB Output is correct
6 Correct 1357 ms 57264 KB Output is correct
7 Correct 1345 ms 57180 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 155 ms 24892 KB Output is correct
4 Correct 393 ms 21944 KB Output is correct
5 Correct 1061 ms 46540 KB Output is correct
6 Correct 1026 ms 46552 KB Output is correct
7 Correct 984 ms 46416 KB Output is correct
8 Correct 1103 ms 46656 KB Output is correct
9 Correct 1176 ms 46428 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 1404 ms 57464 KB Output is correct
7 Correct 1488 ms 57316 KB Output is correct
8 Correct 1489 ms 57288 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 246 ms 26876 KB Output is correct
11 Correct 431 ms 23080 KB Output is correct
12 Correct 1558 ms 57320 KB Output is correct
13 Correct 1481 ms 57328 KB Output is correct
14 Correct 1357 ms 57264 KB Output is correct
15 Correct 1345 ms 57180 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 155 ms 24892 KB Output is correct
19 Correct 393 ms 21944 KB Output is correct
20 Correct 1061 ms 46540 KB Output is correct
21 Correct 1026 ms 46552 KB Output is correct
22 Correct 984 ms 46416 KB Output is correct
23 Correct 1103 ms 46656 KB Output is correct
24 Correct 1176 ms 46428 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 408 ms 23324 KB Output is correct
27 Correct 253 ms 29124 KB Output is correct
28 Correct 1450 ms 59588 KB Output is correct
29 Correct 1435 ms 59524 KB Output is correct
30 Correct 1395 ms 59452 KB Output is correct
31 Correct 1316 ms 59600 KB Output is correct
32 Correct 1315 ms 59516 KB Output is correct