oj.uz

Submission #6103

# Submission time Handle Problem Language Result Execution time Memory
6103 2014-06-19T19:58:31 Z kriii 역사적 조사 (JOI14_historical) C++
75 / 100
 3792 ms 10408 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+Z;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 16 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 40 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
0.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 4 ms 5124 KB Output is correct
8 Correct 12 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 584 ms 6316 KB Output is correct
12 Correct 252 ms 5124 KB Output is correct
13 Correct 1220 ms 5652 KB Output is correct
14 Correct 1728 ms 7900 KB Output is correct
15 Correct 1764 ms 9084 KB Output is correct
16 Incorrect 988 ms 10408 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5264 KB Output is correct
2 Correct 188 ms 5388 KB Output is correct
3 Correct 460 ms 5788 KB Output is correct
4 Correct 748 ms 6328 KB Output is correct
5 Correct 1028 ms 6584 KB Output is correct
6 Correct 1216 ms 6320 KB Output is correct
7 Correct 1104 ms 6320 KB Output is correct
8 Correct 1124 ms 6452 KB Output is correct
9 Correct 828 ms 6588 KB Output is correct
10 Correct 664 ms 6716 KB Output is correct
11 Correct 1284 ms 6848 KB Output is correct
12 Correct 1932 ms 6856 KB Output is correct
13 Correct 2760 ms 7108 KB Output is correct
14 Correct 3680 ms 8304 KB Output is correct
15 Correct 3792 ms 9352 KB Output is correct
16 Correct 3752 ms 8960 KB Output is correct
17 Correct 3744 ms 8700 KB Output is correct
18 Correct 3724 ms 8432 KB Output is correct
19 Correct 3660 ms 8440 KB Output is correct
20 Correct 3636 ms 8308 KB Output is correct
21 Correct 3636 ms 8036 KB Output is correct
22 Correct 3612 ms 8036 KB Output is correct
23 Correct 3608 ms 7896 KB Output is correct
24 Correct 3588 ms 7904 KB Output is correct
25 Correct 308 ms 6720 KB Output is correct