oj.uz

Submission #6094

# Submission time Handle Problem Language Result Execution time Memory
6094 2014-06-19T19:35:02 Z kriii 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 9632 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[100100],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 s == t.s ? e < t.e : s < t.s;}
};
vector<seg> intv[501];

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+e/500].push_back(seg(s,e,i));
	}
	for (int i=0;i<400;i++) if (!intv[i].empty()){
		for (int k=0;k<C;k++) O[k] = B[F+k] = 0; B[1] = 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);
			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 4352 KB Output is correct
2 Correct 0 ms 4352 KB Output is correct
3 Correct 0 ms 4352 KB Output is correct
4 Correct 0 ms 4352 KB Output is correct
5 Correct 0 ms 4352 KB Output is correct
6 Correct 0 ms 4352 KB Output is correct
7 Correct 0 ms 4352 KB Output is correct
8 Correct 0 ms 4352 KB Output is correct
9 Correct 0 ms 4352 KB Output is correct
10 Correct 0 ms 4352 KB Output is correct
11 Correct 0 ms 4352 KB Output is correct
12 Correct 0 ms 4352 KB Output is correct
13 Correct 0 ms 4352 KB Output is correct
14 Correct 0 ms 4352 KB Output is correct
15 Correct 0 ms 4352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4352 KB Output is correct
2 Correct 0 ms 4352 KB Output is correct
3 Correct 0 ms 4352 KB Output is correct
4 Correct 8 ms 4352 KB Output is correct
5 Correct 20 ms 4352 KB Output is correct
6 Correct 32 ms 4352 KB Output is correct
7 Correct 32 ms 4352 KB Output is correct
8 Correct 28 ms 4352 KB Output is correct
9 Correct 28 ms 4352 KB Output is correct
10 Correct 44 ms 4484 KB Output is correct
11 Correct 44 ms 4488 KB Output is correct
12 Correct 52 ms 4488 KB Output is correct
13 Correct 48 ms 4488 KB Output is correct
14 Correct 40 ms 4484 KB Output is correct
15 Correct 40 ms 4484 KB Output is correct
16 Correct 36 ms 4352 KB Output is correct
17 Correct 16 ms 4352 KB Output is correct
18 Correct 40 ms 4492 KB Output is correct
19 Correct 48 ms 4484 KB Output is correct
20 Correct 48 ms 4484 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4352 KB Output is correct
2 Correct 0 ms 4352 KB Output is correct
3 Correct 0 ms 4352 KB Output is correct
4 Correct 0 ms 4352 KB Output is correct
5 Correct 0 ms 4352 KB Output is correct
6 Correct 0 ms 4352 KB Output is correct
7 Correct 8 ms 4352 KB Output is correct
8 Correct 12 ms 4484 KB Output is correct
9 Correct 116 ms 4616 KB Output is correct
10 Correct 116 ms 4352 KB Output is correct
11 Correct 1096 ms 5804 KB Output is correct
12 Correct 276 ms 4352 KB Output is correct
13 Correct 2440 ms 5012 KB Output is correct
14 Correct 3320 ms 6992 KB Output is correct
15 Correct 3452 ms 8316 KB Output is correct
16 Incorrect 2000 ms 9632 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4488 KB Output is correct
2 Correct 236 ms 4620 KB Output is correct
3 Correct 588 ms 5012 KB Output is correct
4 Correct 972 ms 5544 KB Output is correct
5 Correct 1468 ms 5936 KB Output is correct
6 Correct 1764 ms 5540 KB Output is correct
7 Correct 1616 ms 5540 KB Output is correct
8 Correct 1676 ms 5672 KB Output is correct
9 Correct 1268 ms 5804 KB Output is correct
10 Correct 1004 ms 6076 KB Output is correct
11 Correct 1984 ms 6072 KB Output is correct
12 Correct 2996 ms 6068 KB Output is correct
13 Execution timed out 4000 ms 6336 KB Program timed out
14 Halted 0 ms 0 KB -