oj.uz

Submission #31959

# Submission time Handle Problem Language Result Execution time Memory
31959 2017-09-19T14:19:19 Z huynd2001 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 16156 KB 
/*huypheu
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
*/

#include <bits/stdc++.h>
#define int long long
using namespace std;

int le[100007],ri[100007];
int ans[100007];
map <int,int> mymap;
int it[400007];
int blo;
int a[100007],b[100007];
int v[100007];

vector <int> ve;

void update(int node,int l,int r,int x,int p)
{
	// if(node==1) cout << x << " " << p << endl;
	// cout << node << " " << l << " " << r << endl;
	if(l>r || x<l || r<x) return ;
	if(l==r)
	{
		it[node]+=p;
		// cout << node << " " << p << endl;
		return ;
	}
	int mid=(l+r)/2;
	update(node*2,l,mid,x,p);
	update(node*2+1,mid+1,r,x,p);
	it[node]=max(it[node*2],it[node*2+1]);
	return ;
}

int get(int node,int l,int r,int x,int y)
{
	if(l>r || y<l || r<x) return 0;
	if(x<=l && r<=y)
	{
		return it[node];
	}
	int mid=(l+r)/2;
	return max(get(node*2,l,mid,x,y),get(node*2+1,mid+1,r,x,y));
}

bool dcp1(int x,int y)
{
	return (a[x]<a[y]);
}

bool dcp(int x,int y)
{
	if((le[x]/blo)!=(le[y]/blo)) return ((le[x]/blo)<(le[y]/blo));
	else if(ri[x]!=ri[y]) return (ri[x]<ri[y]); else return (le[x]<le[y]);
}

signed main()
{
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	int n,q;
	scanf("%lld %lld",&n,&q);
	// cin >> n >> q;
	blo=(int)sqrt(n);
	// cout << blo << endl;
	int m=0;
	set <int> se;
	for(int i=1;i<=n;i++)
	{
		// cin >> a[i];
		scanf("%lld",&a[i]);
		// cout << a[i] << " ";
		se.insert(a[i]);
		v[i]=i;
		// m=max(m,b[i]);
	}
	sort(v+1,v+n+1,dcp1);
	for(int i=1;i<=n;i++)
	{
		if(i==1 || a[v[i]]!=a[v[i-1]]) m++;
		b[v[i]]=m;
	}
	// for(int i=1;i<=n;i++) cout << b[i] << " " << a[i] << endl;
	// 	cout << endl;
	// for(int i=1;i<=n;i++) cout << b[i] << " ";
	// 	cout << endl;
	// cout << endl;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld %lld",&le[i],&ri[i]);
		ve.push_back(i);
	}
	sort(ve.begin(),ve.end(),dcp);
	int l=le[ve[0]],r=le[ve[0]]-1;
	for(int i=0;i<ve.size();i++)
	{
		// cout << le[ve[i]] << " " << ri[ve[i]] << endl;
		while(l>le[ve[i]])
		{
			l--;
			update(1,1,m,b[l],a[l]);
		}
		while(l<le[ve[i]])
		{
			l++;
			update(1,1,m,b[l-1],-a[l-1]);
		}
		while(r<ri[ve[i]])
		{
			r++;
			update(1,1,m,b[r],a[r]);
		}
		while(r>ri[ve[i]])
		{
			r--;
			update(1,1,m,b[r+1],-a[r+1]);
		}
		ans[ve[i]]=get(1,1,m,1,m);
		// cout << it[1] << endl;
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
		return 0;
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:103:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ve.size();i++)
               ^
historic.cpp:70:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&q);
                          ^
historic.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
historic.cpp:98:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&le[i],&ri[i]);
                                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9848 KB Output is correct
2 Correct 0 ms 9848 KB Output is correct
3 Correct 0 ms 9848 KB Output is correct
4 Correct 0 ms 9848 KB Output is correct
5 Correct 0 ms 9848 KB Output is correct
6 Correct 0 ms 9848 KB Output is correct
7 Correct 0 ms 9848 KB Output is correct
8 Correct 0 ms 9848 KB Output is correct
9 Correct 0 ms 9848 KB Output is correct
10 Correct 0 ms 9848 KB Output is correct
11 Correct 0 ms 9848 KB Output is correct
12 Correct 0 ms 9848 KB Output is correct
13 Correct 0 ms 9848 KB Output is correct
14 Correct 0 ms 9848 KB Output is correct
15 Correct 0 ms 9848 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9848 KB Output is correct
2 Correct 0 ms 9848 KB Output is correct
3 Correct 3 ms 9848 KB Output is correct
4 Correct 13 ms 9848 KB Output is correct
5 Correct 29 ms 10000 KB Output is correct
6 Correct 46 ms 9996 KB Output is correct
7 Correct 49 ms 10000 KB Output is correct
8 Correct 36 ms 9992 KB Output is correct
9 Correct 43 ms 9992 KB Output is correct
10 Correct 73 ms 10132 KB Output is correct
11 Correct 73 ms 10124 KB Output is correct
12 Correct 73 ms 10112 KB Output is correct
13 Correct 69 ms 9980 KB Output is correct
14 Correct 66 ms 9992 KB Output is correct
15 Correct 66 ms 9980 KB Output is correct
16 Correct 43 ms 9992 KB Output is correct
17 Correct 16 ms 9988 KB Output is correct
18 Correct 69 ms 9984 KB Output is correct
19 Correct 73 ms 10136 KB Output is correct
20 Correct 83 ms 10156 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9848 KB Output is correct
2 Correct 0 ms 9848 KB Output is correct
3 Correct 0 ms 9848 KB Output is correct
4 Correct 0 ms 9848 KB Output is correct
5 Correct 0 ms 9848 KB Output is correct
6 Correct 0 ms 9848 KB Output is correct
7 Correct 3 ms 9980 KB Output is correct
8 Correct 13 ms 9980 KB Output is correct
9 Correct 23 ms 10244 KB Output is correct
10 Correct 13 ms 9848 KB Output is correct
11 Correct 129 ms 11468 KB Output is correct
12 Correct 63 ms 9848 KB Output is correct
13 Correct 116 ms 10624 KB Output is correct
14 Correct 199 ms 12576 KB Output is correct
15 Correct 283 ms 14136 KB Output is correct
16 Correct 203 ms 15388 KB Output is correct
17 Correct 66 ms 10320 KB Output is correct
18 Correct 119 ms 11472 KB Output is correct
19 Correct 156 ms 16156 KB Output is correct
20 Correct 99 ms 15000 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 10124 KB Output is correct
2 Correct 496 ms 10348 KB Output is correct
3 Correct 1186 ms 10540 KB Output is correct
4 Correct 2149 ms 11268 KB Output is correct
5 Correct 3019 ms 11432 KB Output is correct
6 Correct 3499 ms 10936 KB Output is correct
7 Correct 3256 ms 11496 KB Output is correct
8 Correct 2493 ms 11472 KB Output is correct
9 Correct 1789 ms 11468 KB Output is correct
10 Correct 726 ms 11468 KB Output is correct
11 Correct 2403 ms 11468 KB Output is correct
12 Execution timed out 4000 ms 11488 KB Execution timed out
13 Halted 0 ms 0 KB -