oj.uz

Submission #168769

# Submission time Handle Problem Language Result Execution time Memory
168769 2019-12-16T05:14:15 Z mhy908 None (KOI17_shell) C++14
0 / 100
 135 ms 11512 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);
    int pv=y;
    for(int i=x; i<=n; i++){
        for(; pv<n; pv++){
            if(get_arr(i, pv)+u<=get_arr(i-1, pv+1))break;
        }
        fin[i]=pv;
    }
    pv=y;
    st[x]=y;
    for(int i=x; i<n; i++){
        bool flag=false;
        for(; pv<=fin[i]; pv++){
            if(get_arr(i, pv)+u>get_arr(i+1, pv-1))break;
            if(pv==fin[i])flag=true;
        }
        if(flag)break;
        st[i+1]=pv;
    }
    for(int i=x; i<=n; i++){
        if(!st[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:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shell.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &a);
             ~~~~~^~~~~~~~~~~~
shell.cpp:79: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 Correct 4 ms 1528 KB Output is correct
2 Incorrect 4 ms 1656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

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

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Incorrect 4 ms 1656 KB Output isn't correct
3 Halted 0 ms 0 KB -