#include <bits/stdc++.h>
using namespace std;
struct P
{
int x,y,z;
bool operator<(const P &a)const{
return x<a.x;
}
};
vector<int> v;
//bitset<4001000> b;
int a,c,i,b,k,n,d,e,m;//dy[15]={0,1,0,-1,-1,1,-1,1},dx[15]={1,0,-1,0,1,1,-1,-1};//
long long l[685130];
int o[335555];
int j[15];
int dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
long long x,y,mod=1000000007;
long long z[133333];
P u[141111];
stack<int> s;
//set<int> s;
queue<int> q;
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
map<int,int> p;
//list<int> l;
//string r;
//char r[1152][1111];
//deque<int> de;
bool as(P a,P b)
{
if(a.x/d!=b.x/d) return a.x<b.x;
return a.y<b.y;
}
void f(int e,int m)
{
l[i+o[m]-1]+=v[o[m]]*e;
for(int h=(i+o[m]-1)/2;h>0;l[h]=max(l[h*2],l[h*2+1]),h>>=1);
}
int main()
{
v.push_back(0);
scanf("%d %d",&a,&b);
d=sqrt(b);
for(int t=1;t<=a;t++)
{
scanf("%d",&o[t]);
if(!p[o[t]]) p[o[t]]=1,v.push_back(o[t]);
}
sort(v.begin(),v.end());
for(int t=1;t<v.size();p[v[t]]=t,t++);
for(int t=1;t<=a;o[t]=p[o[t]],t++);
for(i=1;i<v.size();i<<=1);
n=1;
for(int t=1;t<=b;u[t].z=t,t++)
scanf("%d %d",&u[t].x,&u[t].y);
sort(u+1,u+1+b,as);
for(int t=1;t<=b;t++)
{
for(;m<u[t].y;f(1,++m));
for(;n>u[t].x;f(1,--n));
for(;m>u[t].y;f(-1,m--));
for(;n<u[t].x;f(-1,n++));
z[u[t].z]=l[1];
}
for(int t=1;t<=b;t++)
printf("%lld\n",z[t]);
}
Compilation message
historic.cpp: In function 'int main()':
historic.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int t=1;t<v.size();p[v[t]]=t,t++);
~^~~~~~~~~
historic.cpp:65:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1;i<v.size();i<<=1);
~^~~~~~~~~
historic.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
historic.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&o[t]);
~~~~~^~~~~~~~~~~~
historic.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u[t].x,&u[t].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
2 ms |
640 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
15 |
Correct |
2 ms |
732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
732 KB |
Output is correct |
2 |
Correct |
2 ms |
732 KB |
Output is correct |
3 |
Correct |
3 ms |
732 KB |
Output is correct |
4 |
Correct |
5 ms |
732 KB |
Output is correct |
5 |
Correct |
9 ms |
780 KB |
Output is correct |
6 |
Correct |
16 ms |
924 KB |
Output is correct |
7 |
Correct |
16 ms |
924 KB |
Output is correct |
8 |
Correct |
13 ms |
924 KB |
Output is correct |
9 |
Correct |
14 ms |
924 KB |
Output is correct |
10 |
Correct |
20 ms |
956 KB |
Output is correct |
11 |
Correct |
20 ms |
956 KB |
Output is correct |
12 |
Correct |
20 ms |
956 KB |
Output is correct |
13 |
Correct |
20 ms |
956 KB |
Output is correct |
14 |
Correct |
18 ms |
956 KB |
Output is correct |
15 |
Correct |
19 ms |
956 KB |
Output is correct |
16 |
Correct |
15 ms |
956 KB |
Output is correct |
17 |
Correct |
10 ms |
956 KB |
Output is correct |
18 |
Correct |
18 ms |
1068 KB |
Output is correct |
19 |
Correct |
21 ms |
1068 KB |
Output is correct |
20 |
Correct |
22 ms |
1068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1068 KB |
Output is correct |
2 |
Correct |
2 ms |
1068 KB |
Output is correct |
3 |
Correct |
2 ms |
1068 KB |
Output is correct |
4 |
Correct |
2 ms |
1068 KB |
Output is correct |
5 |
Correct |
4 ms |
1068 KB |
Output is correct |
6 |
Correct |
3 ms |
1068 KB |
Output is correct |
7 |
Correct |
5 ms |
1068 KB |
Output is correct |
8 |
Correct |
9 ms |
1068 KB |
Output is correct |
9 |
Correct |
18 ms |
1216 KB |
Output is correct |
10 |
Correct |
10 ms |
1216 KB |
Output is correct |
11 |
Correct |
78 ms |
3232 KB |
Output is correct |
12 |
Correct |
35 ms |
3232 KB |
Output is correct |
13 |
Correct |
68 ms |
3900 KB |
Output is correct |
14 |
Correct |
133 ms |
8592 KB |
Output is correct |
15 |
Correct |
185 ms |
13408 KB |
Output is correct |
16 |
Correct |
188 ms |
16368 KB |
Output is correct |
17 |
Correct |
39 ms |
16368 KB |
Output is correct |
18 |
Correct |
66 ms |
16368 KB |
Output is correct |
19 |
Correct |
153 ms |
21572 KB |
Output is correct |
20 |
Correct |
107 ms |
21572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
21572 KB |
Output is correct |
2 |
Correct |
122 ms |
21572 KB |
Output is correct |
3 |
Correct |
283 ms |
21572 KB |
Output is correct |
4 |
Correct |
529 ms |
21572 KB |
Output is correct |
5 |
Correct |
732 ms |
21572 KB |
Output is correct |
6 |
Correct |
764 ms |
21572 KB |
Output is correct |
7 |
Correct |
763 ms |
21572 KB |
Output is correct |
8 |
Correct |
664 ms |
21572 KB |
Output is correct |
9 |
Correct |
562 ms |
23700 KB |
Output is correct |
10 |
Correct |
429 ms |
25520 KB |
Output is correct |
11 |
Correct |
738 ms |
27276 KB |
Output is correct |
12 |
Correct |
1160 ms |
29240 KB |
Output is correct |
13 |
Correct |
1747 ms |
31672 KB |
Output is correct |
14 |
Correct |
2472 ms |
35456 KB |
Output is correct |
15 |
Correct |
2647 ms |
39384 KB |
Output is correct |
16 |
Correct |
2642 ms |
40500 KB |
Output is correct |
17 |
Correct |
2515 ms |
42372 KB |
Output is correct |
18 |
Correct |
2462 ms |
44240 KB |
Output is correct |
19 |
Correct |
2544 ms |
46192 KB |
Output is correct |
20 |
Correct |
2380 ms |
48112 KB |
Output is correct |
21 |
Correct |
2352 ms |
50144 KB |
Output is correct |
22 |
Correct |
2328 ms |
52148 KB |
Output is correct |
23 |
Correct |
2333 ms |
54140 KB |
Output is correct |
24 |
Correct |
2314 ms |
56204 KB |
Output is correct |
25 |
Correct |
337 ms |
57092 KB |
Output is correct |