| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 366858 |
2021-02-15T13:12:28 Z |
leinad2 |
None (KOI17_shell) |
C++17 |
|
732 ms |
126444 KB |
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, i, j, k, a, b, B[1510][1510], ans;
char c;
struct tree
{
int seg[6010], lazy[6010];
void busy(int id, int s, int e, int m)
{
seg[id*2]+=(m-s+1)*lazy[id];
seg[id*2+1]+=(e-m)*lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
void update(int id, int s, int e, int l, int r, int v)
{
if(l>r)return;
if(e<l||r<s)return;
if(l<=s&&e<=r)
{
seg[id]+=(e-s+1)*v;
lazy[id]+=v;
return;
}
int m=s+e>>1;
busy(id, s, e, m);
update(id*2, s, m, l, r, v);
update(id*2+1, m+1, e, l, r, v);
seg[id]=seg[id*2]+seg[id*2+1];
}
int get(int id, int s, int e, int l, int r)
{
if(e<l||r<s)return 0;
if(l<=s&&e<=r)return seg[id];
int m=s+e>>1;
busy(id, s, e, m);
return get(id*2, s, m, l, r)+get(id*2+1, m+1, e, l, r);
}
}A[1510];
main()
{
ios_base::sync_with_stdio(!cin.tie(NULL));
cout.tie(NULL);
for(cin>>n;i++<n;)
{
for(j=0;j++<n;)
{
cin>>a;
B[i][j]=max(B[i][j-1], B[i-1][j])+a;
A[i].update(1, 1, n, j, j, B[i][j]);
}
}
for(i=0;i++<n;)ans+=A[i].get(1, 1, n, 1, n);
cout<<ans<<"\n";
for(int q=0;q++<n;)
{
cin>>c>>a>>b;
int pt1=b, pt2=b+1;
if(c=='U')
{
while(pt2<=n)
{
if(A[a-1].get(1, 1, n, pt2, pt2)<=A[a].get(1, 1, n, pt2-1, pt2-1))pt2++;
else break;
}
pt2--;
if(pt1>pt2);
else
ans+=(pt2-pt1+1),
A[a].update(1, 1, n, pt1, pt2, 1);
}
else
{
while(pt2<=n)
{
if(A[a-1].get(1, 1, n, pt2, pt2)<A[a].get(1, 1, n, pt2-1, pt2-1))pt2++;
else break;
}
pt2--;
if(pt1>pt2);
else
ans-=(pt2-pt1+1),
A[a].update(1, 1, n, pt1, pt2, -1);
}
//printf("%lld %lld\n", pt1, pt2);
for(i=a;i++<n;)
{
if(c=='U')
{
while(pt1<=n)
{
if(A[i-1].get(1, 1, n, pt1, pt1)>A[i].get(1, 1, n, pt1-1, pt1-1))break;
else pt1++;
}
pt2++;
while(pt2<=n)
{
if(A[i-1].get(1, 1, n, pt2, pt2)>A[i].get(1, 1, n, pt2-1, pt2-1))pt2++;
else break;
}
pt2--;
if(pt1>pt2)break;
ans+=(pt2-pt1+1);
A[i].update(1, 1, n, pt1, pt2, 1);
}
else
{
while(pt1<=n)
{
if(A[i-1].get(1, 1, n, pt1, pt1)>=A[i].get(1, 1, n, pt1-1, pt1-1))break;
else pt1++;
}
pt2++;
while(pt2<=n)
{
if(A[i-1].get(1, 1, n, pt2, pt2)>=A[i].get(1, 1, n, pt2-1, pt2-1))pt2++;
else break;
}
pt2--;
if(pt1>pt2)break;
ans-=(pt2-pt1+1);
A[i].update(1, 1, n, pt1, pt2, -1);
}
//printf("%lld %lld\n", pt1, pt2);
}
cout<<ans<<"\n";
}
}
Compilation message
shell.cpp: In member function 'void tree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
shell.cpp:27:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m=s+e>>1;
| ~^~
shell.cpp: In member function 'long long int tree::get(long long int, long long int, long long int, long long int, long long int)':
shell.cpp:37:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int m=s+e>>1;
| ~^~
shell.cpp: At global scope:
shell.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main()
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
732 ms |
126444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
