oj.uz

Submission #100942

# Submission time Handle Problem Language Result Execution time Memory
100942 2019-03-15T10:53:10 Z asifthegreat Growing Trees (BOI11_grow) C++14
40 / 100
 1000 ms 4284 KB 
#include <bits/stdc++.h>
#define int long long 
#define all(v) v.begin(),v.end()
#define keepUnique(a) sort(all(a));v.erase(unique(all(v)),v.end())
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 100000;
int ara[N],temp[N];

int32_t main()
{
	int n,m,c,h;
	cin >> n >> m;

	for(int i = 0; i < n;i++){
		cin >> ara[i];
	}
	sort(ara,ara+n);
	char ch;

	while(m--){
		cin >> ch;
		if(ch == 'F'){
			//cout << "hola\n";
			cin >> c >> h;
			int pos = 0;
			int lower = lower_bound(ara,ara+n,h)-ara;
			for (int i = lower; i < n and i < lower+c; i++){
				ara[i]++;
				temp[pos++] = ara[i];
			}
			int k = pos;
			int j = min(n,lower+c);
			int i = 0;
			pos = lower;
			for(;;){
				if(pos == n)break;
				else if(j == n)ara[pos++] = temp[i++];
				else if(i == k)ara[pos++] = ara[j++];
				else if(temp[i] < ara[j]){
					ara[pos++] = temp[i++];
				}
				else ara[pos++] = ara[j++];
			}
			//for(i = 0; i < n;i++){
				//cout << ara[i] << " ";
			//}cout << endl;
		}
		else{
			cin >> c >> h;
			int lower = lower_bound(ara,ara+n,c)-ara;
			int upper = upper_bound(ara,ara+n,h)-ara;
			cout << upper-lower << endl;
		}
	}




	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 2404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 14 ms 384 KB Output is correct
3 Correct 12 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 171 ms 1468 KB Output is correct
6 Correct 251 ms 1912 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 193 ms 1204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 1768 KB Output is correct
2 Correct 271 ms 1884 KB Output is correct
3 Correct 14 ms 384 KB Output is correct
4 Correct 208 ms 1400 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 2080 KB Output is correct
2 Correct 296 ms 1784 KB Output is correct
3 Correct 74 ms 512 KB Output is correct
4 Correct 245 ms 2040 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 2536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 2620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 2524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 3080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 2684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 4284 KB Output is correct