Submission #90278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90278	2018-12-21T04:20:26 Z	YottaByte	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	657 ms	214652 KB

apple

#include <bits/stdc++.h>
using namespace std;

const int N = 1e8 + 1;
int t[2 * N], h[2 * N];
int c;

void push(int v, int l, int r)
{
	if(!h[v]) return;
	if(l == r)
	{
		t[v] = (r - l + 1) * h[v];
		h[v] = 0;
		return;
	}
	else
	{
		t[v] = (r - l + 1) * h[v];
		h[v + v] = h[v];
		h[v + v + 1] = h[v];
		h[v] = 0;
		return;
	}
}

void upd(int v, int l, int r, int ql, int qr)
{
	int mid = l + r >> 1;
	if(r < ql || l > qr) return;
	if(ql <= l && r <= qr)
	{
		h[v] = 1;
		push(v, l, r);
		return;
	}
	else
	{
		upd(v + v, l, mid, ql, qr);
		upd(v + v + 1, mid + 1, r, ql, qr);
	}
	
	push(v + v, l, mid);
	push(v + v + 1, mid + 1, r);
	
	t[v] = t[v + v] + t[v + v + 1];
}

int getsum(int v, int l, int r, int ql, int qr)
{
	push(v, l, r);
	if(r < ql || l > qr) return 0;
	if(ql <= l && r <= qr)
	{
		return t[v];
	}
	else
	{
		int mid = l + r >> 1;
		return getsum(v + v, l, mid, ql, qr) + getsum(v + v + 1, mid + 1, r, ql, qr);
	}
}

main()
{
	int m; cin >> m;
	while(m--)
	{
		int d, l, r;
		cin >> d >> l >> r;
		if(d % 2)
		{
			c = getsum(1, 1, N, l + c, r + c);
			//if(r + c > N - 1) assert(0);
			cout << c << endl;
		}
		else
		{
			upd(1, 1, N, l + c, r + c);
		}
	}
}
/*
6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17
*/

Compilation message

apple.cpp: In function 'void upd(int, int, int, int, int)':
apple.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
apple.cpp: In function 'int getsum(int, int, int, int, int)':
apple.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
apple.cpp: At global scope:
apple.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	684 KB	Output is correct
3	Correct	2 ms	684 KB	Output is correct
4	Correct	38 ms	18976 KB	Output is correct
5	Correct	45 ms	21192 KB	Output is correct
6	Correct	45 ms	21192 KB	Output is correct
7	Correct	46 ms	21228 KB	Output is correct
8	Correct	267 ms	84896 KB	Output is correct
9	Correct	475 ms	106172 KB	Output is correct
10	Correct	554 ms	148296 KB	Output is correct
11	Correct	592 ms	191988 KB	Output is correct
12	Correct	657 ms	214652 KB	Output is correct
13	Runtime error	35 ms	214652 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-