oj.uz

Submission #444584

# Submission time Handle Problem Language Result Execution time Memory
444584 2021-07-14T09:53:35 Z KLPP Distributing Candies (IOI21_candies) C++17
27 / 100
 438 ms 21076 KB 
#include "candies.h"
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
#define INF 1000000000000000LL

struct f{
	lld A; lld B; lld C;
};
f nest(f alpha, f beta){
	return f{min(alpha.A,max(beta.A+alpha.C,alpha.B)),max(beta.B+alpha.C,alpha.B),alpha.C+beta.C};
}
/*
f max(f a, f b){
	
};
f in(f a, f b){
	
};
f operator +(f a, f b){
	
};
struct g{
	f A,B,C;
};*/

class ST{
	f lazy[1000000];
	public:
	void build(int a, int b, int node){
		lazy[node]=f{INF,-INF,0};
		if(a==b)return;
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
	}
	void propag(int a, int b, int node){
		lazy[2*node]=nest(lazy[node],lazy[2*node]);
		lazy[2*node+1]=nest(lazy[node],lazy[2*node+1]);
		lazy[node]=f{INF,-INF,0};
	}
	void update(int a, int b, int node, int x, int y, f operation){
		if(b<x || y<a)return;
		if(x<=a && b<=y){
			lazy[node]=nest(operation,lazy[node]);
			return;
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		update(a,mid,2*node,x,y,operation);
		update(mid+1,b,2*node+1,x,y,operation);
	}
	lld query(int a, int b, int node, int pos){
		if(pos<=a && b<=pos){
			return min(lazy[node].A,max(lazy[node].B,lazy[node].C));
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		if(mid<pos)return query(mid+1,b,2*node+1,pos);
		if(mid>=pos)return query(a,mid,2*node,pos);
	}
	void print(int a, int b, int node){
		cout<<a<<" "<<b<<" "<<node<<" "<<lazy[node].A<<" "<<lazy[node].B<<" "<<lazy[node].C<<endl;
		if(a==b)return;
		int mid=(a+b)/2;
		print(a,mid,2*node);
		print(mid+1,b,2*node+1);
	}
};
ST S;

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    S.build(0,n-1,1);
    rep(q,0,l.size()){
		//S.print(0,n-1,1);
		if(v[q]>0)S.update(0,n-1,1,l[q],r[q],f{c[0],-INF,v[q]});
		if(v[q]<0)S.update(0,n-1,1,l[q],r[q],f{INF,0,v[q]});
		//S.print(0,n-1,1);
	}
    rep(i,0,n){
		s[i]=S.query(0,n-1,1,i);
	}
    return s;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
   80 |     rep(q,0,l.size()){
      |         ~~~~~~~~~~~~             
candies.cpp:80:5: note: in expansion of macro 'rep'
   80 |     rep(q,0,l.size()){
      |     ^~~
candies.cpp: In member function 'lld ST::query(int, int, int, int)':
candies.cpp:64:2: warning: control reaches end of non-void function [-Wreturn-type]
   64 |  }
      |  ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 19756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 174 ms 5092 KB Output is correct
3 Correct 104 ms 16044 KB Output is correct
4 Correct 438 ms 20984 KB Output is correct
5 Correct 399 ms 21060 KB Output is correct
6 Correct 397 ms 21076 KB Output is correct
7 Correct 434 ms 20932 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory 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 -