oj.uz

Submission #168770

# Submission time Handle Problem Language Result Execution time Memory
168770 2019-12-16T05:28:22 Z mhy908 None (KOI17_shell) C++14
0 / 100
 132 ms 8312 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
struct fenwick{
    LL tree[1020];
    LL sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=1010){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen[1010];
int n;
LL arr[1010][1010];
LL ans;
LL get_arr(int x, int y){
    return arr[x][y]+fen[x].sum(y);
}
void query(int x, int y, LL u){
    vector<int> st, fin;
    st.resize(n+10);
    fin.resize(n+10);
    for(int i=1; i<=n; i++)st[i]=n+1;
    fin[x]=y;
    st[x]=y;
    for(int pvx=x, pvy=y;;){
        if(pvy<n&&max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy))+u==max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy)+u))pvy++;
        else pvx++;
        if(pvx>n)break;
        fin[pvx]=pvy;
    }
    for(int pvx=x, pvy=y;;){
        if(pvy<n&&max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy))+u==max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy)+u))pvx++;
        else pvy++;
        if(pvy>n||fin[pvx]<pvy)break;
        st[pvx]=min(st[pvx], pvy);
    }
    for(int i=x; i<=n; i++){
        if(st[i]>fin[i])break;
        ans+=(LL)(fin[i]-st[i]+1)*u;
        fen[i].update(st[i], u);
        fen[i].update(fin[i]+1, -u);
    }
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            LL a;
            scanf("%lld", &a);
            arr[i][j]=max(arr[i-1][j], arr[i][j-1])+a;
            ans+=arr[i][j];
        }
    }
    printf("%lld\n", ans);
    for(int i=1; i<=n; i++){
        char c;
        int a, b;
        scanf(" %c %d %d", &c, &a, &b);
        if(c=='U')query(a, b, 1);
        else query(a, b, -1);
        printf("%lld\n", ans);
    }
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shell.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &a);
             ~~~~~^~~~~~~~~~~~
shell.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &c, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 8312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -