oj.uz

Submission #493843

# Submission time Handle Problem Language Result Execution time Memory
493843 2021-12-13T07:22:24 Z gurkot Distributing Candies (IOI21_candies) C++17
40 / 100
 1525 ms 59712 KB 
#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.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 7 ms 836 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 57536 KB Output is correct
2 Correct 1480 ms 57280 KB Output is correct
3 Correct 1525 ms 57324 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 253 ms 26884 KB Output is correct
3 Correct 433 ms 23272 KB Output is correct
4 Correct 1495 ms 57492 KB Output is correct
5 Correct 1435 ms 57304 KB Output is correct
6 Correct 1338 ms 57300 KB Output is correct
7 Incorrect 1393 ms 59712 KB Output isn't correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 153 ms 24900 KB Output is correct
4 Correct 397 ms 22092 KB Output is correct
5 Correct 1038 ms 46452 KB Output is correct
6 Correct 1012 ms 46388 KB Output is correct
7 Correct 954 ms 46488 KB Output is correct
8 Correct 1054 ms 46476 KB Output is correct
9 Correct 1168 ms 46568 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 7 ms 836 KB Output is correct
6 Correct 1393 ms 57536 KB Output is correct
7 Correct 1480 ms 57280 KB Output is correct
8 Correct 1525 ms 57324 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 253 ms 26884 KB Output is correct
11 Correct 433 ms 23272 KB Output is correct
12 Correct 1495 ms 57492 KB Output is correct
13 Correct 1435 ms 57304 KB Output is correct
14 Correct 1338 ms 57300 KB Output is correct
15 Incorrect 1393 ms 59712 KB Output isn't correct