oj.uz

Submission #404246

# Submission time Handle Problem Language Result Execution time Memory
404246 2021-05-14T02:41:29 Z lyc None (KOI17_shell) C++14
100 / 100
 586 ms 35308 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 1505;

int N, A[mxN][mxN], dp[mxN][mxN];

struct Fenwick {
    int ft[mxN];

    Fenwick() {
        memset(ft,0,sizeof ft);
    }

    void update(int a, int b) {
        for (; a <= N; a += a&-a) ft[a] += b;
    }

    void update(int a, int b, int c) {
        update(a,c);
        update(b+1,-c);
    }

    long long query(int a) {
        long long r = 0;
        for (; a; a -= a&-a) r += ft[a];
        return r;
    }
} ft[mxN];

long long S = 0;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N){
        FOR(j,1,N){
            cin >> A[i][j];
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + A[i][j];

            ft[i].update(j,j,dp[i][j]);
            S += dp[i][j];
        }
    }

    cout << S << '\n';
    FOR(i,1,N){
        char op;
        int R, C, V;
        cin >> op >> R >> C;
        V = (op == 'U' ? 1 : -1);

        A[R][C] += V;

        int s = C, e = C+1;
        while (R <= N) {
            while (s < e) {
                int ov = ft[R].query(s);
                int nv = max(ft[R-1].query(s), ft[R].query(s-1)) + A[R][s];
                //TRACE(R _ s _ ov _ nv);
                if (nv != ov) break;
                ++s;
            }

            if (s < e) {
                while (e <= N) {
                    int ov = ft[R].query(e);
                    int nv = max(ft[R-1].query(e), ft[R].query(e-1)+V) + A[R][e];
                    //TRACE(R _ e _ ov _ nv);
                    if (nv == ov) break;
                    ++e;
                }

                ft[R].update(s,e-1,V);
                //TRACE(R _ "UPDATE [)" _ s _ e);
                S += (e-s) * V;
                ++R;
            } else break;
        }

        cout << S << '\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10060 KB Output is correct
2 Correct 6 ms 10060 KB Output is correct
3 Correct 6 ms 10092 KB Output is correct
4 Correct 6 ms 10060 KB Output is correct
5 Correct 7 ms 10060 KB Output is correct
6 Correct 7 ms 10060 KB Output is correct
7 Correct 6 ms 9980 KB Output is correct
8 Correct 6 ms 10060 KB Output is correct
9 Correct 6 ms 10060 KB Output is correct
10 Correct 7 ms 10188 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 31272 KB Output is correct
2 Correct 233 ms 31172 KB Output is correct
3 Correct 235 ms 31248 KB Output is correct
4 Correct 228 ms 31416 KB Output is correct
5 Correct 236 ms 31256 KB Output is correct
6 Correct 235 ms 31164 KB Output is correct
7 Correct 236 ms 31276 KB Output is correct
8 Correct 240 ms 31300 KB Output is correct
9 Correct 223 ms 31224 KB Output is correct
10 Correct 230 ms 31240 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10060 KB Output is correct
2 Correct 6 ms 10060 KB Output is correct
3 Correct 6 ms 10092 KB Output is correct
4 Correct 6 ms 10060 KB Output is correct
5 Correct 7 ms 10060 KB Output is correct
6 Correct 7 ms 10060 KB Output is correct
7 Correct 6 ms 9980 KB Output is correct
8 Correct 6 ms 10060 KB Output is correct
9 Correct 6 ms 10060 KB Output is correct
10 Correct 266 ms 31272 KB Output is correct
11 Correct 233 ms 31172 KB Output is correct
12 Correct 235 ms 31248 KB Output is correct
13 Correct 228 ms 31416 KB Output is correct
14 Correct 236 ms 31256 KB Output is correct
15 Correct 235 ms 31164 KB Output is correct
16 Correct 236 ms 31276 KB Output is correct
17 Correct 240 ms 31300 KB Output is correct
18 Correct 223 ms 31224 KB Output is correct
19 Correct 230 ms 31240 KB Output is correct
20 Correct 7 ms 10188 KB Output is correct
21 Correct 279 ms 32760 KB Output is correct
22 Correct 275 ms 32828 KB Output is correct
23 Correct 278 ms 32848 KB Output is correct
24 Correct 550 ms 32864 KB Output is correct
25 Correct 503 ms 34916 KB Output is correct
26 Correct 528 ms 34920 KB Output is correct
27 Correct 239 ms 31168 KB Output is correct
28 Correct 238 ms 31272 KB Output is correct
29 Correct 274 ms 35136 KB Output is correct
30 Correct 276 ms 35184 KB Output is correct
31 Correct 571 ms 35308 KB Output is correct
32 Correct 586 ms 35292 KB Output is correct
33 Correct 239 ms 31216 KB Output is correct
34 Correct 246 ms 31212 KB Output is correct