oj.uz

Submission #6093

# Submission time Handle Problem Language Result Execution time Memory
6093 2014-06-19T19:26:04 Z kriii 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 8388 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; long long R[100010],B[1<<18],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+Z] = R[x] * O[x];
	x = (x + Z) >> 1;
	while (x){
		B[x] = max(B[x*2],B[x*2+1]);
		x >>= 1;
	}
}

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<<=1);

	for (int i=0,s,e;i<Q;i++){
		scanf ("%d %d",&s,&e); s--;
		intv[s/400+e/400].push_back(seg(s,e,i));
	}
	for (int i=0;i<500;i++) if (!intv[i].empty()){
		for (int k=0;k<2*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);
			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 5616 KB Output is correct
2 Correct 0 ms 5616 KB Output is correct
3 Correct 0 ms 5616 KB Output is correct
4 Correct 0 ms 5616 KB Output is correct
5 Correct 0 ms 5616 KB Output is correct
6 Correct 0 ms 5616 KB Output is correct
7 Correct 0 ms 5616 KB Output is correct
8 Correct 0 ms 5616 KB Output is correct
9 Correct 0 ms 5616 KB Output is correct
10 Correct 0 ms 5616 KB Output is correct
11 Correct 0 ms 5616 KB Output is correct
12 Correct 0 ms 5616 KB Output is correct
13 Correct 0 ms 5616 KB Output is correct
14 Correct 0 ms 5616 KB Output is correct
15 Correct 0 ms 5616 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5616 KB Output is correct
2 Correct 0 ms 5616 KB Output is correct
3 Correct 0 ms 5616 KB Output is correct
4 Correct 0 ms 5616 KB Output is correct
5 Correct 0 ms 5616 KB Output is correct
6 Correct 0 ms 5616 KB Output is correct
7 Correct 12 ms 5616 KB Output is correct
8 Correct 16 ms 5748 KB Output is correct
9 Correct 140 ms 5880 KB Output is correct
10 Correct 84 ms 5616 KB Output is correct
11 Correct 1160 ms 7204 KB Output is correct
12 Correct 296 ms 5616 KB Output is correct
13 Correct 3188 ms 6276 KB Output is correct
14 Execution timed out 4000 ms 8388 KB Program timed out
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 5752 KB Output is correct
2 Correct 268 ms 6012 KB Output is correct
3 Correct 668 ms 6412 KB Output is correct
4 Correct 1252 ms 6936 KB Output is correct
5 Correct 1888 ms 7204 KB Output is correct
6 Correct 2144 ms 6936 KB Output is correct
7 Correct 2072 ms 6940 KB Output is correct
8 Correct 1872 ms 7072 KB Output is correct
9 Correct 1320 ms 7200 KB Output is correct
10 Correct 736 ms 7332 KB Output is correct
11 Correct 1872 ms 7464 KB Output is correct
12 Correct 3588 ms 7464 KB Output is correct
13 Execution timed out 4000 ms 7728 KB Program timed out
14 Halted 0 ms 0 KB -