oj.uz

Submission #6104

# Submission time Handle Problem Language Result Execution time Memory
6104 2014-06-19T19:59:53 Z kriii 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 6992 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[1001];

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/100].push_back(seg(s,e,i));
	}
	for (int i=0;i<1000;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 5144 KB Output is correct
2 Correct 0 ms 5144 KB Output is correct
3 Correct 0 ms 5144 KB Output is correct
4 Correct 0 ms 5144 KB Output is correct
5 Correct 0 ms 5144 KB Output is correct
6 Correct 0 ms 5144 KB Output is correct
7 Correct 0 ms 5144 KB Output is correct
8 Correct 0 ms 5144 KB Output is correct
9 Correct 0 ms 5144 KB Output is correct
10 Correct 0 ms 5144 KB Output is correct
11 Correct 0 ms 5144 KB Output is correct
12 Correct 0 ms 5144 KB Output is correct
13 Correct 0 ms 5144 KB Output is correct
14 Correct 0 ms 5144 KB Output is correct
15 Correct 0 ms 5144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5144 KB Output is correct
2 Correct 0 ms 5144 KB Output is correct
3 Correct 0 ms 5144 KB Output is correct
4 Correct 0 ms 5144 KB Output is correct
5 Correct 8 ms 5144 KB Output is correct
6 Correct 20 ms 5144 KB Output is correct
7 Correct 20 ms 5144 KB Output is correct
8 Correct 16 ms 5144 KB Output is correct
9 Correct 16 ms 5144 KB Output is correct
10 Correct 28 ms 5276 KB Output is correct
11 Correct 28 ms 5276 KB Output is correct
12 Correct 28 ms 5276 KB Output is correct
13 Correct 28 ms 5276 KB Output is correct
14 Correct 24 ms 5144 KB Output is correct
15 Correct 24 ms 5276 KB Output is correct
16 Correct 20 ms 5144 KB Output is correct
17 Correct 8 ms 5144 KB Output is correct
18 Correct 24 ms 5276 KB Output is correct
19 Correct 24 ms 5276 KB Output is correct
20 Correct 28 ms 5276 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5144 KB Output is correct
2 Correct 0 ms 5144 KB Output is correct
3 Correct 0 ms 5144 KB Output is correct
4 Correct 0 ms 5144 KB Output is correct
5 Correct 0 ms 5144 KB Output is correct
6 Correct 4 ms 5144 KB Output is correct
7 Correct 20 ms 5144 KB Output is correct
8 Correct 16 ms 5276 KB Output is correct
9 Correct 132 ms 5408 KB Output is correct
10 Correct 172 ms 5144 KB Output is correct
11 Correct 2692 ms 6728 KB Output is correct
12 Correct 272 ms 5144 KB Output is correct
13 Execution timed out 4000 ms 5800 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5276 KB Output is correct
2 Correct 280 ms 5540 KB Output is correct
3 Correct 844 ms 5936 KB Output is correct
4 Correct 1608 ms 6464 KB Output is correct
5 Correct 2584 ms 6728 KB Output is correct
6 Correct 3216 ms 6464 KB Output is correct
7 Correct 3036 ms 6464 KB Output is correct
8 Correct 3232 ms 6596 KB Output is correct
9 Correct 2448 ms 6860 KB Output is correct
10 Correct 2004 ms 6992 KB Output is correct
11 Execution timed out 4000 ms 6992 KB Program timed out
12 Halted 0 ms 0 KB -