oj.uz

Submission #493842

# Submission time Handle Problem Language Result Execution time Memory
493842 2021-12-13T07:17:45 Z gurkot Distributing Candies (IOI21_candies) C++17
40 / 100
 1515 ms 60400 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include "candies.h"
using namespace std;
const int nmax=200010,  qmin=0,  qmax=1;
const long long inf=10000000000LL;
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 0 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 1336 ms 59424 KB Output is correct
2 Correct 1404 ms 60400 KB Output is correct
3 Correct 1425 ms 60364 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 244 ms 29228 KB Output is correct
3 Correct 417 ms 25216 KB Output is correct
4 Correct 1515 ms 59536 KB Output is correct
5 Correct 1481 ms 59636 KB Output is correct
6 Incorrect 1311 ms 59628 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 152 ms 26912 KB Output is correct
4 Correct 389 ms 23152 KB Output is correct
5 Correct 1039 ms 48704 KB Output is correct
6 Correct 1006 ms 48668 KB Output is correct
7 Correct 965 ms 48752 KB Output is correct
8 Correct 1075 ms 48664 KB Output is correct
9 Correct 1167 ms 48676 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1336 ms 59424 KB Output is correct
7 Correct 1404 ms 60400 KB Output is correct
8 Correct 1425 ms 60364 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 244 ms 29228 KB Output is correct
11 Correct 417 ms 25216 KB Output is correct
12 Correct 1515 ms 59536 KB Output is correct
13 Correct 1481 ms 59636 KB Output is correct
14 Incorrect 1311 ms 59628 KB Output isn't correct
15 Halted 0 ms 0 KB -