oj.uz

Submission #444611

# Submission time Handle Problem Language Result Execution time Memory
444611 2021-07-14T11:37:36 Z KLPP Distributing Candies (IOI21_candies) C++17
3 / 100
 127 ms 8864 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 1000000000000000000LL
lld arr[1000000];
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{0,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);
	}
	f query2(int a, int b, int node, int pos){
		if(pos<=a && b<=pos){
			return lazy[node];
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		if(mid<pos)return query2(mid+1,b,2*node+1,pos);
		if(mid>=pos)return query2(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;
vector<int> a,b;
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);
    if(n<=2000 && l.size()<=2000){
		    rep(i,0,n)arr[i]=0;
    rep(q,0,l.size()){
		rep(i,l[q],r[q]+1){
			if(v[q]>0){
				arr[i]=min(arr[i]+v[q],(lld)c[i]);
			}else{
				arr[i]=max(arr[i]+v[q],0LL);
			}
		}
	}
	rep(i,0,n)s[i]=arr[i];
	return s;
	}
    rep(i,0,n+1)arr[i]=0;
    rep(i,0,l.size()){
		arr[l[i]]+=v[i];
		arr[r[i]+1]-=v[i];
	}
	s[0]=arr[0];
	rep(i,1,n)s[i]=arr[i]+(s[i-1]);
	rep(i,0,n){
		s[i]=min(s[i],c[i]);
	}
    /*a.resize(n);
    b.resize(n);
    S.build(0,l.size()-1,1);
    rep(i,0,l.size()){
		//S.print(0,n-1,1);
		if(v[i]>0){
			S.update(0,l.size()-1,1,0,i-1,f{INF,-INF,v[i]});
			S.update(0,l.size()-1,1,i,i,f{INF,-INF,0});
		}
		if(v[i]<0){
			S.update(0,l.size()-1,1,0,i-1,f{INF,-INF,v[i]});
			S.update(0,l.size()-1,1,0,i-1,f{INF,0,0});
		}
		//S.print(0,n-1,1);
	}
	vector<pair<lld,lld> >V;
    rep(i,0,l.size()){
		cout<<S.query2(0,l.size()-1,1,i).B<<" "<<S.query2(0,l.size()-1,1,i).C<<endl;
		V.push_back({S.query2(0,l.size()-1,1,i).B,S.query2(0,l.size()-1,1,i).C});
	}*/
    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++)
......
   90 |     rep(q,0,l.size()){
      |         ~~~~~~~~~~~~             
candies.cpp:90:5: note: in expansion of macro 'rep'
   90 |     rep(q,0,l.size()){
      |     ^~~
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++)
......
  103 |     rep(i,0,l.size()){
      |         ~~~~~~~~~~~~             
candies.cpp:103:5: note: in expansion of macro 'rep'
  103 |     rep(i,0,l.size()){
      |     ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 62 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 63 ms 5052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Incorrect 127 ms 8864 KB Output isn't correct
7 Halted 0 ms 0 KB -