Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. ×

### stostap's blog

By stostap, history, 12 months ago, Hi,

I was playing one of the contests from Opentrains today, but system was very unreliable:

• I saw a lot of times result "Check failed"

• When I sent the same solution, but different languages, I got a few times "Check failed" and once "AC"

• The same solution on different attempts get PE18, PE34, PE36 etc.

• When I was trying to submit solution, I got a lot of times "Disk write error (disk full?)" message, and my solution wasn't submitted.

I believe there are problems with Opentrains. Can someone who has access check and fix it?

Thanks! By stostap, history, 4 years ago, Hi community,

I'm big fan of treaps, but this task makes me feel stupid. https://www.e-olymp.com/en/problems/2957

There is no English translate for some reason. Task: Given N single-element lists with integers 1..10^9, perform next queries:

• merge L R -> take two already exist lists and create a new one, equal concat(L,R)
• head L -> create two new lists: first contains first element of L, second — the rest of L.
• tail L -> create two new lists: first contains all L without last element, second — last element.

For every new list you need to output sum of it's elements.

I've did it with persistent treap — for every merge query: merge(root[L], root[R], root[++versions]), for head — split(root[L], root[nextV()], root[nextV()], 1) for tail — split(root[L], root[nextV()], root[nextV()], cnt[root[L]]-1);

But this fails with "Memory Limit" as for every query it creates at least Log new nodes

typedef long long LL;
#define N 13000005
#define MOD 1000000007
int root , c;
struct Treap
{
int sum[N];
int nodecnt;
int L[N] , R[N] , cnt[N];
int key[N];
void clear() {
nodecnt = 0;
}
Treap () {clear();}
bool hey(int A , int B) {
return (LL)rand() * (cnt[A] + cnt[B]) < (LL)cnt[A] * RAND_MAX;
}
int newnode(int x) {
++ nodecnt , L[nodecnt] = R[nodecnt] = 0;
cnt[nodecnt] = 1 , key[nodecnt] = x, sum[nodecnt] = x;
return nodecnt;
}
int copynode(int A) {
if (!A) return 0;
++ nodecnt , L[nodecnt] = L[A] , R[nodecnt] = R[A];
cnt[nodecnt] = cnt[A] , key[nodecnt] = key[A], sum[nodecnt] = sum[A];
if (nodecnt == 5000000 &mdash; 100) {
printf("TREAP\n");
exit(0);
}
return nodecnt;
}
void pushup(int x) {
cnt[x] = 1;
sum[x] = key[x];
if (L[x]) {
cnt[x] += cnt[L[x]];
sum[x] = (sum[x] + sum[L[x]]) % MOD;
}
if (R[x]) {
cnt[x] += cnt[R[x]];
sum[x] = (sum[x] + sum[R[x]]) % MOD;
}
}
void merge(int& p , int x , int y) {
if (!x || !y) {
p = 0;
if (x) p = copynode(x);
if (y) p = copynode(y);
}
else if ( hey(x , y) ) {
p = copynode(x);
merge(R[p] , R[x] , y) , pushup(p);
}
else {
p = copynode(y);
merge(L[p] , x , L[y]) , pushup(p);
}
}
void split(int p , int& x , int& y , int size) {
if (!size) {
x = 0 , y = copynode(p);
return;
}
if (cnt[L[p]] >= size) {
y = copynode(p);
split(L[p] , x , L[y] , size) , pushup(y);
}
else {
x = copynode(p);
split(R[p] , R[x] , y , size &mdash; cnt[L[p]] &mdash; 1) , pushup(x);
}
}
void print(int p) {
if (L[p]) print(L[p]);
printf("%d ", key[p]);
if (R[p]) print(R[p]);
}
};
Treap T;
char s;

int main(void) {
int n;
scanf("%d", &n);
int version = 0;
REP(i, n) {
int x;
scanf("%d", &x);
root[++version] = T.newnode(x);
}

int q;
scanf("%d", &q);
REP(i, q) {
if (version >= 300005 &mdash; 50) {
printf("TREAP2\n");
exit(0);
}
scanf("%s", &s);
if (s == 'm') {
int x,y;
scanf("%d%d", &x, &y);
T.merge(root[++version], root[x], root[y]);
printf("%d\n", T.sum[root[version]]);
}

if (s == 'h') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}

if (s == 't') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], T.cnt[root[x]] - 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}
}
}


Any ideas how to improve it? By stostap, history, 5 years ago, http://www.spoj.com/problems/TROOPS/

Hi, could you give any hints why dp approach here giving WA?

REP(i, n) {
int x,y,z;
scanf("%d%d%d", &x, &y, &z);
FOR(j, max(1, y - x + 1), y + 1) {
a[j] = max(a[j], z);
}
}
int sum = 0;
REP(i, T) {
sum += a[i];
}


Thanks! spoj, wa,
By stostap, 10 years ago, Why I can't watch my code for submissions and tests? code,
By stostap, 10 years ago, Can anyone explain me solution with interval tree? or any other solution?

P.S. I understand Russian By stostap, 10 years ago, Please, help. Give me some hints ... By stostap, 10 years ago, I know solution with O(n * 2 ^ n). Why it is working with n = 24? n * 2 ^ n = 402653184

I know that this task is for circle intersection. Who can give me more hint's? cf 8,
By stostap, 10 years ago,  