oj.uz

Submission #163193

# Submission time Handle Problem Language Result Execution time Memory
163193 2019-11-11T18:00:02 Z TadijaSebez 역사적 조사 (JOI14_historical) C++11
100 / 100
 358 ms 7024 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int S=317;
ll sum[N],mx;
vector<int> val;
int l[N],r[N],a[N];
vector<int> Qs[N/S+1];
void Add(int x)
{
	sum[x]+=val[x];
	mx=max(mx,sum[x]);
}
void Del(int x){ sum[x]-=val[x];}
ll ans[N];
int main()
{
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),val.pb(a[i]);
	sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
	for(int i=1;i<=n;i++) a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin();
	for(int i=1;i<=q;i++) scanf("%i %i",&l[i],&r[i]),Qs[l[i]/S].pb(i);
	for(int i=0;i*S<=n;i++)
	{
		int s=i*S,e=(i+1)*S-1;
		sort(Qs[i].begin(),Qs[i].end(),[&](int i, int j){ return r[i]<r[j];});
		int ptr=e;
		for(int id:Qs[i])
		{
			if(r[id]<=e)
			{
				for(int j=l[id];j<=r[id];j++) Add(a[j]);
				ans[id]=mx;
				for(int j=l[id];j<=r[id];j++) Del(a[j]);
				mx=0;
			}
			else
			{
				while(ptr<r[id]) Add(a[++ptr]);
				ll tmp=mx;
				for(int j=l[id];j<=e;j++) Add(a[j]);
				ans[id]=mx;
				for(int j=l[id];j<=e;j++) Del(a[j]);
				mx=tmp;
			}
		}
		for(int j=e+1;j<=ptr;j++) Del(a[j]);
		mx=0;
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:28:7: warning: unused variable 's' [-Wunused-variable]
   int s=i*S,e=(i+1)*S-1;
       ^
historic.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
historic.cpp:22:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),val.pb(a[i]);
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
historic.cpp:25:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&l[i],&r[i]),Qs[l[i]/S].pb(i);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 8 ms 504 KB Output is correct
6 Correct 11 ms 632 KB Output is correct
7 Correct 11 ms 632 KB Output is correct
8 Correct 12 ms 632 KB Output is correct
9 Correct 11 ms 632 KB Output is correct
10 Correct 11 ms 672 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 11 ms 760 KB Output is correct
14 Correct 11 ms 632 KB Output is correct
15 Correct 11 ms 760 KB Output is correct
16 Correct 11 ms 632 KB Output is correct
17 Correct 11 ms 632 KB Output is correct
18 Correct 12 ms 632 KB Output is correct
19 Correct 11 ms 760 KB Output is correct
20 Correct 11 ms 632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 7 ms 692 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 12 ms 1144 KB Output is correct
11 Correct 102 ms 5184 KB Output is correct
12 Correct 35 ms 2036 KB Output is correct
13 Correct 65 ms 2928 KB Output is correct
14 Correct 104 ms 4704 KB Output is correct
15 Correct 92 ms 6896 KB Output is correct
16 Correct 219 ms 5172 KB Output is correct
17 Correct 109 ms 2540 KB Output is correct
18 Correct 176 ms 5200 KB Output is correct
19 Correct 175 ms 6512 KB Output is correct
20 Correct 89 ms 3700 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1016 KB Output is correct
2 Correct 42 ms 1528 KB Output is correct
3 Correct 69 ms 2168 KB Output is correct
4 Correct 93 ms 2904 KB Output is correct
5 Correct 123 ms 3416 KB Output is correct
6 Correct 150 ms 4212 KB Output is correct
7 Correct 184 ms 4756 KB Output is correct
8 Correct 212 ms 5744 KB Output is correct
9 Correct 250 ms 6304 KB Output is correct
10 Correct 272 ms 6100 KB Output is correct
11 Correct 283 ms 6224 KB Output is correct
12 Correct 332 ms 6352 KB Output is correct
13 Correct 296 ms 6508 KB Output is correct
14 Correct 332 ms 6856 KB Output is correct
15 Correct 358 ms 7024 KB Output is correct
16 Correct 351 ms 6920 KB Output is correct
17 Correct 349 ms 6896 KB Output is correct
18 Correct 348 ms 6896 KB Output is correct
19 Correct 335 ms 6896 KB Output is correct
20 Correct 330 ms 6772 KB Output is correct
21 Correct 326 ms 6896 KB Output is correct
22 Correct 321 ms 6896 KB Output is correct
23 Correct 332 ms 6764 KB Output is correct
24 Correct 315 ms 6840 KB Output is correct
25 Correct 278 ms 6916 KB Output is correct