oj.uz

Submission #6106

# Submission time Handle Problem Language Result Execution time Memory
6106 2014-06-19T20:01:38 Z kriii 역사적 조사 (JOI14_historical) C++
100 / 100
 3788 ms 10672 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

map<int, int> chk;
int N,Q,C,X[100010],O[100010],Z,F; long long R[100010],B[200100],A[100010];

struct seg{
	seg(int s_, int e_, int i_){s = s_; e = e_; i = i_;}
	int s,e,i;
	bool operator <(const seg t)const{return e != t.e ? e < t.e : s < t.s;}
};
vector<seg> intv[201];

void upt(int x, int p)
{
	x = X[x]; O[x] += p;
	B[x+F] = R[x] * O[x];
	x = (x + F + 2) / 4;
	while (x){
		B[x] = max(max(B[x*4-2],B[x*4-1]),max(B[x*4],B[x*4+1]));
		x = (x + 2) / 4;
	}
}

int main()
{
	scanf ("%d %d",&N,&Q);
	for (int i=0;i<N;i++){
		scanf ("%d",&X[i]);
		chk[X[i]] = 0;
	}
	
	for (map<int, int>::iterator I = chk.begin(); I != chk.end(); I++) R[C] = I->first, I->second = C++;
	for (int i=0;i<N;i++) X[i] = chk[X[i]];
	for (Z=1;Z<C;Z<<=2) F += Z; F++;

	for (int i=0,s,e;i<Q;i++){
		scanf ("%d %d",&s,&e); s--;
		intv[s/500].push_back(seg(s,e,i));
	}
	for (int i=0;i<200;i++) if (!intv[i].empty()){
		for (int k=0;k<F+C;k++) B[k] = 0;
		for (int k=0;k<C;k++) O[k] = 0;
		int s = 0, e = 0;
		sort(intv[i].begin(),intv[i].end());
		for (int j=0;j<intv[i].size();j++){
			while (e < intv[i][j].e) upt(e++,1);
			//while (e > intv[i][j].e) upt(--e,-1);
			while (s < intv[i][j].s) upt(s++,-1);
			while (s > intv[i][j].s) upt(--s,1);
			A[intv[i][j].i] = B[1];
		}
	}

	for (int i=0;i<Q;i++) printf ("%lld\n",A[i]);

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5124 KB Output is correct
2 Correct 0 ms 5124 KB Output is correct
3 Correct 0 ms 5124 KB Output is correct
4 Correct 0 ms 5124 KB Output is correct
5 Correct 0 ms 5124 KB Output is correct
6 Correct 0 ms 5124 KB Output is correct
7 Correct 0 ms 5124 KB Output is correct
8 Correct 0 ms 5124 KB Output is correct
9 Correct 0 ms 5124 KB Output is correct
10 Correct 0 ms 5124 KB Output is correct
11 Correct 0 ms 5124 KB Output is correct
12 Correct 0 ms 5124 KB Output is correct
13 Correct 0 ms 5124 KB Output is correct
14 Correct 0 ms 5124 KB Output is correct
15 Correct 0 ms 5124 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5124 KB Output is correct
2 Correct 0 ms 5124 KB Output is correct
3 Correct 4 ms 5124 KB Output is correct
4 Correct 8 ms 5124 KB Output is correct
5 Correct 20 ms 5124 KB Output is correct
6 Correct 32 ms 5124 KB Output is correct
7 Correct 32 ms 5124 KB Output is correct
8 Correct 24 ms 5124 KB Output is correct
9 Correct 24 ms 5124 KB Output is correct
10 Correct 44 ms 5256 KB Output is correct
11 Correct 44 ms 5256 KB Output is correct
12 Correct 44 ms 5256 KB Output is correct
13 Correct 44 ms 5260 KB Output is correct
14 Correct 36 ms 5256 KB Output is correct
15 Correct 32 ms 5260 KB Output is correct
16 Correct 32 ms 5124 KB Output is correct
17 Correct 16 ms 5124 KB Output is correct
18 Correct 40 ms 5264 KB Output is correct
19 Correct 44 ms 5260 KB Output is correct
20 Correct 44 ms 5256 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5124 KB Output is correct
2 Correct 0 ms 5124 KB Output is correct
3 Correct 0 ms 5124 KB Output is correct
4 Correct 0 ms 5124 KB Output is correct
5 Correct 0 ms 5124 KB Output is correct
6 Correct 0 ms 5124 KB Output is correct
7 Correct 0 ms 5124 KB Output is correct
8 Correct 8 ms 5256 KB Output is correct
9 Correct 88 ms 5388 KB Output is correct
10 Correct 72 ms 5124 KB Output is correct
11 Correct 580 ms 6316 KB Output is correct
12 Correct 252 ms 5124 KB Output is correct
13 Correct 1212 ms 5652 KB Output is correct
14 Correct 1716 ms 7900 KB Output is correct
15 Correct 1776 ms 9084 KB Output is correct
16 Correct 1100 ms 10408 KB Output is correct
17 Correct 228 ms 5388 KB Output is correct
18 Correct 516 ms 5916 KB Output is correct
19 Correct 1252 ms 10672 KB Output is correct
20 Correct 340 ms 10008 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 5264 KB Output is correct
2 Correct 196 ms 5388 KB Output is correct
3 Correct 456 ms 5788 KB Output is correct
4 Correct 732 ms 6328 KB Output is correct
5 Correct 1084 ms 6584 KB Output is correct
6 Correct 1220 ms 6320 KB Output is correct
7 Correct 1100 ms 6320 KB Output is correct
8 Correct 1120 ms 6452 KB Output is correct
9 Correct 816 ms 6588 KB Output is correct
10 Correct 664 ms 6716 KB Output is correct
11 Correct 1288 ms 6848 KB Output is correct
12 Correct 1932 ms 6856 KB Output is correct
13 Correct 2756 ms 7108 KB Output is correct
14 Correct 3660 ms 8304 KB Output is correct
15 Correct 3788 ms 9352 KB Output is correct
16 Correct 3752 ms 8960 KB Output is correct
17 Correct 3716 ms 8700 KB Output is correct
18 Correct 3696 ms 8432 KB Output is correct
19 Correct 3668 ms 8440 KB Output is correct
20 Correct 3660 ms 8308 KB Output is correct
21 Correct 3640 ms 8036 KB Output is correct
22 Correct 3592 ms 8036 KB Output is correct
23 Correct 3596 ms 7896 KB Output is correct
24 Correct 3592 ms 7904 KB Output is correct
25 Correct 304 ms 6720 KB Output is correct