oj.uz

Submission #6090

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5628 KB Output is correct
2 Correct 4 ms 5628 KB Output is correct
3 Correct 8 ms 5628 KB Output is correct
4 Correct 16 ms 5628 KB Output is correct
5 Correct 32 ms 5628 KB Output is correct
6 Correct 72 ms 5628 KB Output is correct
7 Correct 64 ms 5628 KB Output is correct
8 Correct 68 ms 5628 KB Output is correct
9 Correct 72 ms 5628 KB Output is correct
10 Correct 68 ms 5760 KB Output is correct
11 Correct 68 ms 5760 KB Output is correct
12 Correct 68 ms 5760 KB Output is correct
13 Correct 68 ms 5760 KB Output is correct
14 Correct 64 ms 5628 KB Output is correct
15 Correct 64 ms 5760 KB Output is correct
16 Correct 72 ms 5628 KB Output is correct
17 Correct 84 ms 5628 KB Output is correct
18 Correct 68 ms 5760 KB Output is correct
19 Correct 68 ms 5760 KB Output is correct
20 Correct 64 ms 5760 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5628 KB Output is correct
2 Correct 0 ms 5628 KB Output is correct
3 Correct 0 ms 5628 KB Output is correct
4 Correct 0 ms 5628 KB Output is correct
5 Correct 4 ms 5628 KB Output is correct
6 Correct 16 ms 5628 KB Output is correct
7 Correct 40 ms 5628 KB Output is correct
8 Correct 28 ms 5760 KB Output is correct
9 Correct 240 ms 5892 KB Output is correct
10 Correct 1388 ms 5628 KB Output is correct
11 Execution timed out 4000 ms 7208 KB Program timed out
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 5760 KB Output is correct
2 Correct 620 ms 6024 KB Output is correct
3 Correct 1324 ms 6420 KB Output is correct
4 Correct 2448 ms 6948 KB Output is correct
5 Correct 3800 ms 7212 KB Output is correct
6 Execution timed out 4000 ms 6948 KB Program timed out
7 Halted 0 ms 0 KB -