Submission #403475

#	Time	Username	Problem	Language	Result	Execution time	Memory
403475		tqbfjotld	조개 줍기 (KOI17_shell)	C++14	0 / 100	805 ms	317932 KiB

shell

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

set<int> ups[1505];
int fenwick[1505][1505];

void upd(int pos, int val, int num){
    while (pos<1505){
        fenwick[pos][num]+=val;
        pos+=pos&-pos;
    }
}
int qu(int pos, int num){
    int ans = 0;
    while (pos>0){
        ans += fenwick[pos][num];
        pos-=pos&-pos;
    }
    return ans;
}

int initarr[1505][1505];
int v2[1505][1505];
int n;
int curans = 0;
vector<pair<int,int> > to_up;
vector<pair<int,int> > to_left;

void incr(int x, int y){
    int curval = qu(x,y);
    if (x!=1 && y!=n){
        int t1 = qu(x-1,y+1);
        if (t1==curval+1){
            to_up.push_back({x,y+1});
        }
    }
    if (x!=n && y!=1){
        int t2 = qu(x+1,y-1);
        if (t2==curval){
            //printf("pushing %lld %lld\n",x+1,y);
            to_left.push_back({x+1,y});
            incr(x+1,y);
        }
    }
}

void decr(int x, int y){
    int curval = qu(x,y);
    if (x!=1 && y!=n){
        int t1 = qu(x-1,y+1);
        if (t1==curval){
            to_left.push_back({x,y+1});
        }
    }
    if (x!=n && y!=1){
        int t2 = qu(x+1,y-1);
        if (t2==curval-1){
            to_up.push_back({x+1,y});
            decr(x+1,y);
        }
    }
}

void set_up(int x, int y){
    //printf("%lld %lld set up\n",x,y);
    assert(ups[y].lower_bound(x)==ups[y].end() || (*ups[y].lower_bound(x))!=x);
    assert(y!=1);
    ups[y].insert(x);
}
void set_left(int x, int y){
    //printf("%lld %lld set left\n",x,y);
    assert((*ups[y].lower_bound(x))==x);
    assert(x!=1);
    ups[y].erase(ups[y].lower_bound(x));
}

void incr2(int x, int y, int minbound){
    auto it = ups[y].lower_bound(minbound+1);
    int bound;
    if (it==ups[y].end()){
        bound = n;
    }
    else bound = (*it)-1;
    curans += bound-x+1;
    upd(x,1,y);
    upd(bound+1,-1,y);
    if (y!=n){
        auto it2 = ups[y+1].lower_bound(x);
        if (it2==ups[y+1].end() || (*it2)>bound) return;
        incr2((*it2),y+1,bound);
    }
}
void decr2(int x, int y, int minbound){
    auto it = ups[y].lower_bound(minbound+1);
    int bound;
    if (it==ups[y].end()){
        bound = n;
    }
    else bound = (*it)-1;
    curans -= bound-x+1;
    upd(x,-1,y);
    upd(bound+1,1,y);
    if (y!=n){
        auto it2 = ups[y+1].lower_bound(x);
        if (it2==ups[y+1].end() || (*it2)>bound) return;
        decr2((*it2),y+1,bound);
    }
}

main(){
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        for (int y = 1; y<=n; y++){
            scanf("%lld",&initarr[x][y]);
        }
    }
    for (int x = 1; x<=n; x++){
        for (int y = 1; y<=n; y++){
            if (x==1&&y==1){
                v2[x][y] = initarr[x][y];
            }
            else if (x==1){
                v2[x][y] = v2[x][y-1]+initarr[x][y];
                ups[y].insert(x);
            }
            else if (y==1){
                v2[x][y] = v2[x-1][y]+initarr[x][y];
            }
            else if (v2[x-1][y]>v2[x][y-1]){
                v2[x][y] = v2[x-1][y]+initarr[x][y];
            }
            else{
                v2[x][y] = v2[x][y-1]+initarr[x][y];
                ups[y].insert(x);
            }
            curans += v2[x][y];
            upd(x,v2[x][y],y);
            upd(x+1,-v2[x][y],y);
        }
    }
    printf("%lld\n",curans);
    for (int q = 0; q<n; q++){
        char c;
        int a,b;
        scanf(" %c",&c);
        scanf("%lld%lld",&a,&b);
        if (c=='U'){
            incr(a,b);
            //printf("incr donw\n");
            for (auto x : to_left){
                set_left(x.first,x.second);
            }
            incr2(a,b,a);
            for (auto x : to_up){
                set_up(x.first,x.second);
            }
        }
        else{
            decr(a,b);
            for (auto x : to_left){
                set_left(x.first,x.second);
            }
            decr2(a,b,a);
            for (auto x : to_up){
                set_up(x.first,x.second);
            }
        }
        to_left.clear();
        to_up.clear();
        printf("%lld\n",curans);
    }
}

Compilation message (stderr)

shell.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main(){
      | ^~~~
shell.cpp: In function 'int main()':
shell.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
shell.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |             scanf("%lld",&initarr[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
shell.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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