oj.uz

Submission #6105

# Submission time Handle Problem Language Result Execution time Memory
6105 2014-06-19T20:00:36 Z kriii 역사적 조사 (JOI14_historical) C++
40 / 100
 4000 ms 10748 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[51];

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/2000].push_back(seg(s,e,i));
	}
	for (int i=0;i<50;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 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 20 ms 5124 KB Output is correct
5 Correct 56 ms 5124 KB Output is correct
6 Correct 96 ms 5124 KB Output is correct
7 Correct 96 ms 5256 KB Output is correct
8 Correct 76 ms 5124 KB Output is correct
9 Correct 76 ms 5124 KB Output is correct
10 Correct 140 ms 5276 KB Output is correct
11 Correct 140 ms 5292 KB Output is correct
12 Correct 140 ms 5276 KB Output is correct
13 Correct 140 ms 5276 KB Output is correct
14 Correct 120 ms 5260 KB Output is correct
15 Correct 116 ms 5256 KB Output is correct
16 Correct 92 ms 5124 KB Output is correct
17 Correct 40 ms 5124 KB Output is correct
18 Correct 120 ms 5288 KB Output is correct
19 Correct 136 ms 5272 KB Output is correct
20 Correct 144 ms 5256 KB Output is correct

Subtask #3
25.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 8 ms 5256 KB Output is correct
9 Correct 36 ms 5388 KB Output is correct
10 Correct 24 ms 5124 KB Output is correct
11 Correct 184 ms 6376 KB Output is correct
12 Correct 176 ms 5124 KB Output is correct
13 Correct 352 ms 5652 KB Output is correct
14 Correct 516 ms 7776 KB Output is correct
15 Correct 544 ms 8992 KB Output is correct
16 Correct 380 ms 10316 KB Output is correct
17 Correct 80 ms 5416 KB Output is correct
18 Correct 172 ms 5992 KB Output is correct
19 Correct 384 ms 10748 KB Output is correct
20 Correct 140 ms 10028 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 5260 KB Output is correct
2 Correct 544 ms 5444 KB Output is correct
3 Correct 1176 ms 5836 KB Output is correct
4 Correct 1704 ms 6384 KB Output is correct
5 Correct 2216 ms 6652 KB Output is correct
6 Correct 2468 ms 6396 KB Output is correct
7 Correct 2040 ms 6248 KB Output is correct
8 Correct 1972 ms 6548 KB Output is correct
9 Correct 1356 ms 6580 KB Output is correct
10 Correct 1040 ms 6808 KB Output is correct
11 Correct 2004 ms 6816 KB Output is correct
12 Correct 3064 ms 6820 KB Output is correct
13 Execution timed out 4000 ms 7216 KB Program timed out
14 Halted 0 ms 0 KB -