Submission #404415

#	Time	Username	Problem	Language	Result	Execution time	Memory
404415		joelau	조개 줍기 (KOI17_shell)	C++14	100 / 100	724 ms	35396 KiB

shell

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

int N, A[1500][1500];
long long ft[1500][1501];

void update (int n, int x, long long v) {
    x++;
    while (x <= N) ft[n][x] += v, x += x & -x;
}

void update (int n, int a, int b, long long v) {
    update(n,a,v); update(n,b+1,-v);
}

long long query (int n, int x) {
    x++;
    long long ans = 0;
    while (x) ans += ft[n][x], x -= x & -x;
    return ans;
}

long long f(int x, int y) {
    long long ans = 0;
    if (x != 0) ans = max(ans,query(x-1,y));
    if (y != 0) ans = max(ans,query(x,y-1));
    return ans + A[x][y];
}

int main() {
    scanf("%d", &N);
    memset(ft,0,sizeof(ft));
    long long ans = 0;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        scanf("%d", &A[i][j]);
        long long val = f(i,j);
        update(i,j,j,val);
        ans += val;
    }
    printf("%lld\n", ans);
    for (int a = 0; a < N; ++a) {
        char c; int x,y; scanf(" %c %d %d", &c, &x, &y); x--, y--;
        int v = c == 'U' ? 1 : -1, s = y, e = y+1;
        A[x][y] += v, ans += v;
        update(x,s,s,v);
        while (e < N && f(x,e) != query(x,e)) update(x,e,e,v), e++, ans += v;
        for (int i = x+1; i < N; ++i) {
            while (s < e && f(i,s) == query(i,s)) s++;
            update(i,s,e-1,v), ans += (e-s) * v;
            while (e < N && f(i,e) != query(i,e)) update(i,e,e,v), e++, ans += v;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
shell.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d", &A[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~
shell.cpp:42:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         char c; int x,y; scanf(" %c %d %d", &c, &x, &y); x--, y--;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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