Submission #366858

#	Time	Username	Problem	Language	Result	Execution time	Memory
366858		leinad2	조개 줍기 (KOI17_shell)	C++17	0 / 100	732 ms	126444 KiB

shell

#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 (stderr)

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()
      |      ^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54