oj.uz

Submission #6101

# Submission time Handle Problem Language Result Execution time Memory
6101 2014-06-19T19:53:28 Z kriii 역사적 조사 (JOI14_historical) C++
5 / 100
 952 ms 9632 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[100100],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[201];

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/1000].push_back(seg(s,e,i));
	}
	for (int i=0;i<100;i++) if (!intv[i].empty()){
		for (int k=0;k<C;k++) O[k] = B[F+k] = 0; B[1] = 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 4344 KB Output is correct
2 Correct 0 ms 4344 KB Output is correct
3 Correct 0 ms 4344 KB Output is correct
4 Correct 0 ms 4344 KB Output is correct
5 Correct 0 ms 4344 KB Output is correct
6 Correct 0 ms 4344 KB Output is correct
7 Correct 0 ms 4344 KB Output is correct
8 Correct 0 ms 4344 KB Output is correct
9 Correct 0 ms 4344 KB Output is correct
10 Correct 0 ms 4344 KB Output is correct
11 Correct 0 ms 4344 KB Output is correct
12 Correct 0 ms 4344 KB Output is correct
13 Correct 0 ms 4344 KB Output is correct
14 Correct 0 ms 4344 KB Output is correct
15 Correct 0 ms 4344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4344 KB Output is correct
2 Correct 0 ms 4344 KB Output is correct
3 Correct 4 ms 4344 KB Output is correct
4 Correct 12 ms 4344 KB Output is correct
5 Correct 32 ms 4344 KB Output is correct
6 Correct 52 ms 4344 KB Output is correct
7 Correct 52 ms 4344 KB Output is correct
8 Correct 40 ms 4344 KB Output is correct
9 Correct 44 ms 4344 KB Output is correct
10 Incorrect 76 ms 4480 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4344 KB Output is correct
2 Correct 0 ms 4344 KB Output is correct
3 Correct 0 ms 4344 KB Output is correct
4 Correct 0 ms 4344 KB Output is correct
5 Correct 0 ms 4344 KB Output is correct
6 Correct 0 ms 4344 KB Output is correct
7 Correct 4 ms 4344 KB Output is correct
8 Correct 12 ms 4476 KB Output is correct
9 Correct 48 ms 4608 KB Output is correct
10 Correct 36 ms 4344 KB Output is correct
11 Correct 312 ms 5540 KB Output is correct
12 Correct 196 ms 4344 KB Output is correct
13 Correct 632 ms 4872 KB Output is correct
14 Correct 896 ms 6984 KB Output is correct
15 Correct 952 ms 8312 KB Output is correct
16 Incorrect 588 ms 9632 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4492 KB Output is correct
2 Incorrect 284 ms 4608 KB Output isn't correct
3 Halted 0 ms 0 KB -