This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
struct PNode {
vi v,t;
ll qry (ll curt){
/*
cout << "queried: " << curt << "\n";
for (auto i: v) cout << i << " ";
cout << endl;
for (auto i: t) cout << i << " ";
cout << endl;
*/
auto itr = upper_bound(t.begin(),t.end(),curt);
ll idx = distance(t.begin(),itr)-1;
//cout << v[idx] << endl;
return v[idx];
}
ll lst_qry(){
return v.back();
}
void inc_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(lst_qry()+vn);
t.push_back(tn);
}else{
v[v.size()-1] += vn;
}
}
void change_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(vn);
t.push_back(tn);
}else{
v[v.size()-1] = vn;
}
}
PNode (){ v = vi{0}; t = vi{0}; }
};
class SegTree {
private:
vector<PNode> st;
ll n;
ll left (ll x){ return (x << 1) ; }
ll right (ll x){ return (x << 1) + 1; }
void update (ll i, ll l, ll r, ll idx, ll inc, ll t){
// assumed that t is updated increasingly
if (r >= idx && idx >= l){
if (l == r){
st[i].inc_update(inc,t);
}else{
//cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
ll m = (l+r)/2;
update(left(i),l,m,idx,inc,t);
update(right(i),m+1,r,idx,inc,t);
st[i].change_update(st[left(i)].lst_qry()+st[right(i)].lst_qry(),t);
}
//cout << i << " " << t << " , " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
}
}
ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){
//cout << i << " " << l << " " << r << " " << ql << " " << qr << endl;
if (qr >= r && l >= ql){
/*
cout << "queried: \n";
cout << "params: " << i << " " << l << " " << r << endl;
cout << "result: " << st[i].qry(t) << endl;
*/
return st[i].qry(t);
}else if (l > qr || ql > r){
return 0;
}else{
ll m = (l+r)/2;
ll lres = query(left(i),l,m,ql,qr,t);
ll rres = query(right(i),m+1,r,ql,qr,t);
return lres+rres;
}
}
public:
SegTree (){}
SegTree(ll _n): n(_n){
st.resize(4*n);
}
void update (ll idx, ll inc, ll t){
update(1,0,n-1,idx,inc,t);
}
ll query (ll ql, ll qr, ll t){
return query(1,0,n-1,ql,qr,t);
}
};
SegTree st;
ll n;
void init(int _n, int a[], int b[]) {
n = _n;
st = SegTree(n+1);
vii itvls;
for (ll i = 0; n > i; i++) itvls.emplace_back(a[i],b[i]);
sort(itvls.begin(),itvls.end());
for (auto i: itvls){
//cout << i.F << " " << i.S << endl;
st.update(i.S,1,i.F);
}
}
int can(int m, int k[]) {
map<ll,ll> ctr;
for (ll i = 0; m > i; i++){
if (ctr.find(k[i]) == ctr.end()) ctr[k[i]] = 0;
ctr[k[i]]+=k[i];
}
vi vals;
for (auto i: ctr){
vals.push_back(i.F);
}
vals.push_back(n+1);
vi byBucket;
byBucket.assign(vals.size(),0);
auto itr = ctr.begin();
/*
cout << itr->F << " " << itr->S << endl;
cout << "vals:\n";
for (auto i: vals) cout << i << " ";
cout << endl;
*/
for (ll i = 0; vals.size() > i+1; i++){
for (ll j = i; vals.size() > j+1; j++){
//cout << "i: " << i << " j: " << j << endl;
ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j];
//cout << vals[j] << " " << vals[j+1] << " " << vals[i] << ": " << rmv << endl;
//cout << "itr: " << itr->F << " " << itr->S << endl;
rmv = min(rmv,itr->S);
itr->S -= rmv;
byBucket[j] += rmv;
}
/*
cout << itr->F << " " << itr->S << endl;
for (auto i: byBucket) cout << i << " ";
cout << endl;
*/
itr++;
}
for (auto i: ctr){
//cout << i.F << " " << i.S << endl;
if (i.S > 0){ return 0; }
}
//cout << "1\n";
return 1;
}
Compilation message (stderr)
teams.cpp: In function 'int can(int, int*)':
teams.cpp:148:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
148 | for (ll i = 0; vals.size() > i+1; i++){
| ~~~~~~~~~~~~^~~~~
teams.cpp:149:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
149 | for (ll j = i; vals.size() > j+1; j++){
| ~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |