I'm not sure if we are allowed to discuss about other judges on codeforces, however solving problems from IOI is not available on codeforces.
I was trying to solve problem Holiday from IOI 2014. I know two judges that have this problem available — Oj.uz and Wcipeg. Namely my solution works on Wcipeg and gets accepted, while it fails on Oj.uz due to error message: Execution killed with signal 9 (could be triggered by violating memory limits). I don't know whether my solution is correct or not, also if it is correct why it doesn't work on Oj.uz
I have given my both codes below, since the way those two judges work is different, wcipeg gives us the variables on standard input, while on oj.uz we need to code function that will solve the problem.
Wcipeg code
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];
class node {
public:
ll sum;
int cnt;
node *leftchild, *rightchild;
node(ll _sum, ll _cnt) {
sum = _sum;
cnt = _cnt;
}
node(node *a, node *b) {
leftchild = a;
rightchild = b;
sum = a->sum + b->sum;
cnt = a->cnt + b->cnt;
}
};
node* build(int li=1, int ri=d) {
if(li == ri) return new node(0LL, 0LL);
else {
int mid = (li + ri) / 2;
return new node(build(li, mid), build(mid+1, ri));
}
}
node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) {
if(li == ri) {
return new node(curr->sum + uval, curr->cnt + 1);
}
else {
int mid = (li + ri) / 2;
if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
}
}
ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
ll total = p->cnt - pm->cnt;
if(k == 0) return 0LL;
if(total < k) return (p->sum - pm->sum);
if(li == ri) {
return k * value[li];
}
else {
int mid = (li + ri) / 2;
ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total_right, li, mid);
}
}
node *prefix[maxn];
set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];
void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
if(l > r) return;
int mid = (l + r) / 2;
dp[mid] = -1;
int optmid = -1;
for(int i=optl;i<=optr;i++) {
ll walk = i - mid + min(start - mid, i - start);
ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk));
if(curr > dp[mid]) {
dp[mid] = curr;
optmid = i;
}
}
solvedp(l, mid-1, optl, optmid);
solvedp(mid+1, r, optmid, optr);
}
int main() {
cin>>n>>start>>c;
start++;
for(int i=0;i<n;i++) {
cin>>arr[i];
st.insert(arr[i]);
}
int br = 1;
for(int i:st) {
value[br] = i;
ind[i] = br++;
}
d = br - 1;
for(int i=n-1;i>=0;i--) {
arr[i+1] = ind[arr[i]];
}
node *curr = build();
prefix[0] = curr;
for(int i=1;i<=n;i++) {
curr = update(curr, arr[i], value[arr[i]]);
prefix[i] = curr;
}
solvedp();
ll result = 0LL;
for(int i=1;i<=n;i++) {
result = max(result, dp[i]);
}
cout<<result<<"\n";
return 0;
}
Oj.uz code
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];
class node {
public:
ll sum;
int cnt;
node *leftchild, *rightchild;
node(ll _sum, ll _cnt) {
sum = _sum;
cnt = _cnt;
}
node(node *a, node *b) {
leftchild = a;
rightchild = b;
sum = a->sum + b->sum;
cnt = a->cnt + b->cnt;
}
};
node* build(int li=1, int ri=d) {
if(li == ri) return new node(0LL, 0LL);
else {
int mid = (li + ri) / 2;
return new node(build(li, mid), build(mid+1, ri));
}
}
node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) {
if(li == ri) {
return new node(curr->sum + uval, curr->cnt + 1);
}
else {
int mid = (li + ri) / 2;
if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
}
}
ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
ll total = p->cnt - pm->cnt;
if(k == 0) return 0LL;
if(total < k) return (p->sum - pm->sum);
if(li == ri) {
return k * value[li];
}
else {
int mid = (li + ri) / 2;
ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total_right, li, mid);
}
}
node *prefix[maxn];
set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];
void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
if(l > r) return;
int mid = (l + r) / 2;
dp[mid] = -1;
int optmid = -1;
for(int i=optl;i<=optr;i++) {
ll walk = i - mid + min(start - mid, i - start);
ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk));
if(curr > dp[mid]) {
dp[mid] = curr;
optmid = i;
}
}
solvedp(l, mid-1, optl, optmid);
solvedp(mid+1, r, optmid, optr);
}
ll findMaxAttraction(int _n, int _start, int _c, int _attractions[]) {
n = _n;
start = _start;
c = _c;
start++;
for(int i=0;i<n;i++) {
arr[i] = _attractions[i];
st.insert(arr[i]);
}
int br = 1;
for(int i:st) {
value[br] = i;
ind[i] = br++;
}
d = br - 1;
for(int i=n-1;i>=0;i--) {
arr[i+1] = ind[arr[i]];
}
node *curr = build();
prefix[0] = curr;
for(int i=1;i<=n;i++) {
curr = update(curr, arr[i], value[arr[i]]);
prefix[i] = curr;
}
solvedp();
ll result = 0LL;
for(int i=1;i<=n;i++) {
result = max(result, dp[i]);
}
return result;
}
If you had similar experiences, please share them, also I would like to know why my solutions fails on oj.uz.
