oj.uz

답안 #6091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6091 2014-06-19T19:24:18 Z kriii 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 7204 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

map<int, int> chk;
const int Z = 1<<17;
int N,Q,C,X[100010],O[100010]; long long R[100010],B[Z*2],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 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5616 KB Output is correct
2 Correct 4 ms 5616 KB Output is correct
3 Correct 4 ms 5616 KB Output is correct
4 Correct 20 ms 5616 KB Output is correct
5 Correct 40 ms 5616 KB Output is correct
6 Correct 76 ms 5616 KB Output is correct
7 Correct 68 ms 5616 KB Output is correct
8 Correct 76 ms 5616 KB Output is correct
9 Correct 80 ms 5616 KB Output is correct
10 Correct 76 ms 5748 KB Output is correct
11 Correct 72 ms 5748 KB Output is correct
12 Correct 72 ms 5748 KB Output is correct
13 Correct 72 ms 5748 KB Output is correct
14 Correct 76 ms 5752 KB Output is correct
15 Correct 72 ms 5748 KB Output is correct
16 Correct 76 ms 5616 KB Output is correct
17 Correct 84 ms 5616 KB Output is correct
18 Correct 64 ms 5748 KB Output is correct
19 Correct 72 ms 5748 KB Output is correct
20 Correct 76 ms 5748 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 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 4 ms 5616 KB Output is correct
6 Correct 4 ms 5616 KB Output is correct
7 Correct 24 ms 5616 KB Output is correct
8 Correct 24 ms 5748 KB Output is correct
9 Correct 196 ms 5880 KB Output is correct
10 Correct 1028 ms 5616 KB Output is correct
11 Execution timed out 4000 ms 7200 KB Program timed out
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 5752 KB Output is correct
2 Correct 476 ms 6012 KB Output is correct
3 Correct 920 ms 6412 KB Output is correct
4 Correct 1572 ms 6936 KB Output is correct
5 Correct 2356 ms 7204 KB Output is correct
6 Correct 2960 ms 6936 KB Output is correct
7 Correct 3708 ms 6940 KB Output is correct
8 Execution timed out 4000 ms 7068 KB Program timed out
9 Halted 0 ms 0 KB -