oj.uz

Submission #168885

# Submission time Handle Problem Language Result Execution time Memory
168885 2019-12-17T00:34:55 Z mhy908 None (KOI17_shell) C++14
100 / 100
 666 ms 44960 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[1520];
    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<=1500){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen[1510];
int n;
LL arr[1510][1510];
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=x+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(pvx<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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2040 KB Output is correct
2 Correct 5 ms 2040 KB Output is correct
3 Correct 5 ms 2040 KB Output is correct
4 Correct 5 ms 2036 KB Output is correct
5 Correct 6 ms 2040 KB Output is correct
6 Correct 6 ms 2040 KB Output is correct
7 Correct 5 ms 2044 KB Output is correct
8 Correct 5 ms 2040 KB Output is correct
9 Correct 5 ms 2040 KB Output is correct
10 Correct 5 ms 1912 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 25304 KB Output is correct
2 Correct 238 ms 25228 KB Output is correct
3 Correct 276 ms 40440 KB Output is correct
4 Correct 291 ms 24824 KB Output is correct
5 Correct 289 ms 24788 KB Output is correct
6 Correct 238 ms 25232 KB Output is correct
7 Correct 237 ms 25336 KB Output is correct
8 Correct 285 ms 24824 KB Output is correct
9 Correct 282 ms 24696 KB Output is correct
10 Correct 283 ms 24476 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2040 KB Output is correct
2 Correct 5 ms 2040 KB Output is correct
3 Correct 5 ms 2040 KB Output is correct
4 Correct 5 ms 2036 KB Output is correct
5 Correct 6 ms 2040 KB Output is correct
6 Correct 6 ms 2040 KB Output is correct
7 Correct 5 ms 2044 KB Output is correct
8 Correct 5 ms 2040 KB Output is correct
9 Correct 5 ms 2040 KB Output is correct
10 Correct 238 ms 25304 KB Output is correct
11 Correct 238 ms 25228 KB Output is correct
12 Correct 276 ms 40440 KB Output is correct
13 Correct 291 ms 24824 KB Output is correct
14 Correct 289 ms 24788 KB Output is correct
15 Correct 238 ms 25232 KB Output is correct
16 Correct 237 ms 25336 KB Output is correct
17 Correct 285 ms 24824 KB Output is correct
18 Correct 282 ms 24696 KB Output is correct
19 Correct 283 ms 24476 KB Output is correct
20 Correct 371 ms 44476 KB Output is correct
21 Correct 377 ms 44504 KB Output is correct
22 Correct 381 ms 44472 KB Output is correct
23 Correct 649 ms 44712 KB Output is correct
24 Correct 619 ms 44612 KB Output is correct
25 Correct 636 ms 44664 KB Output is correct
26 Correct 237 ms 25504 KB Output is correct
27 Correct 271 ms 40440 KB Output is correct
28 Correct 367 ms 44664 KB Output is correct
29 Correct 363 ms 44412 KB Output is correct
30 Correct 635 ms 44960 KB Output is correct
31 Correct 666 ms 44700 KB Output is correct
32 Correct 236 ms 25208 KB Output is correct
33 Correct 285 ms 24568 KB Output is correct
34 Correct 5 ms 1912 KB Output is correct