oj.uz

답안 #170636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170636 2019-12-25T22:37:55 Z jacynkaa 섬 항해 (CEOI13_adriatic) C++17
100 / 100
 404 ms 137108 KB 
#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#pragma GCC optimize("-O3")
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define bck(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(c) (c).begin(), (c).end()
#define what(x) cerr << #x << " is " << x << endl;

#define debug(X)                             \
    cerr << #X << endl;                      \
    rep(i, MAXN)                             \
    {                                        \
        rep(j, MAXN) cerr << X[i][j] << " "; \
        cerr << endl;                        \
    }

const int MAXN = 2500;
const int MAXQ = (int)3e5;
long long dp[MAXN][MAXN];
int sum[MAXN][MAXN];
bool pole[MAXN][MAXN];
int lef[MAXN][MAXN];
int down[MAXN][MAXN];
long long ans[MAXQ];
pii Q[MAXQ];
int n;

pii rotate(pii tmp)
{
    return {MAXN - tmp.st - 1, MAXN - tmp.nd - 1};
}

void input()
{
    cin >> n;
    rep(i, n)
    {
        cin >> Q[i].st >> Q[i].nd;
        Q[i].st--;
        Q[i].nd--;
    }
}

void calcsum()
{
    rep(i, MAXN) rep(j, MAXN)
    {
        pole[i][j] = false;
        sum[i][j] = 0;
    }
    rep(i, n)
    {

        pole[Q[i].st][Q[i].nd] = true;
        sum[Q[i].st][Q[i].nd] = 1;
    }
    bck(i, MAXN) rep(j, MAXN) if (i != MAXN - 1) sum[i][j] += sum[i + 1][j];
    bck(i, MAXN) rep(j, MAXN) if (j != 0) sum[i][j] += sum[i][j - 1];
}
void calclef()
{
    rep(i, MAXN) rep(j, MAXN) lef[i][j] = MAXN;
    rep(i, MAXN) rep(j, MAXN)
    {
        if (pole[i][j])
            lef[i][j] = min(lef[i][j], j);
        if (i != 0)
            lef[i][j] = min(lef[i][j], lef[i - 1][j]);
        if (j != 0)
            lef[i][j] = min(lef[i][j], lef[i][j - 1]);
    }
}

void calcdown()
{
    rep(i, MAXN) rep(j, MAXN) down[i][j] = 0;
    bck(i, MAXN) bck(j, MAXN)
    {
        if (pole[i][j])
            down[i][j] = max(down[i][j], i);
        if (i != MAXN - 1)
            down[i][j] = max(down[i][j], down[i + 1][j]);
        if (j != MAXN - 1)
            down[i][j] = max(down[i][j], down[i][j + 1]);
    }
}

void calcdp()
{
    rep(i, MAXN) bck(j, MAXN) dp[i][j] = 0;
    bck(i, MAXN) rep(j, MAXN)
    {
        int a = (i == MAXN - 1 || j == MAXN - 1) ? i : max(down[i + 1][j + 1], i);
        int b = (i == 0 || j == 0) ? j : min(lef[i - 1][j - 1], j);
        dp[i][j] = dp[a][b] + sum[i][j];
        //  cerr << i << " " << j << " " << a << " " << b <<
    }
}

void solve()
{
    calcsum();
    calcdown();
    calclef();
    calcdp();
    rep(i, n)
        ans[i] += dp[Q[i].st][Q[i].nd];
}

void rotate()
{
    rep(i, n)
        Q[i] = rotate(Q[i]);
}

void deb()
{
    return;
    debug(pole);
    debug(sum);
    debug(lef);
    debug(down);
    debug(dp);
    rep(i, n) cerr << Q[i].st << " " << Q[i].nd << endl;
    cerr << endl;
}

main()
{
    _upgrade;
    input();
    solve();
    deb();
    rotate();
    solve();
    deb();
    rep(i, n) cout << ans[i] + n - 3 << endl;
}

Compilation message

adriatic.cpp:140:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 129016 KB Output is correct
2 Correct 309 ms 128760 KB Output is correct
3 Correct 317 ms 128804 KB Output is correct
4 Correct 291 ms 128888 KB Output is correct
5 Correct 290 ms 128892 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 128896 KB Output is correct
2 Correct 288 ms 128872 KB Output is correct
3 Correct 291 ms 128888 KB Output is correct
4 Correct 289 ms 128988 KB Output is correct
5 Correct 293 ms 128944 KB Output is correct
6 Correct 296 ms 128888 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 128940 KB Output is correct
2 Correct 292 ms 129016 KB Output is correct
3 Correct 299 ms 128884 KB Output is correct
4 Correct 293 ms 128884 KB Output is correct
5 Correct 292 ms 129016 KB Output is correct
6 Correct 316 ms 129016 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 129656 KB Output is correct
2 Correct 300 ms 129592 KB Output is correct
3 Correct 332 ms 129616 KB Output is correct
4 Correct 298 ms 129528 KB Output is correct
5 Correct 334 ms 129592 KB Output is correct
6 Correct 350 ms 129656 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 137108 KB Output is correct
2 Correct 391 ms 136776 KB Output is correct
3 Correct 404 ms 136768 KB Output is correct
4 Correct 377 ms 136440 KB Output is correct
5 Correct 379 ms 136944 KB Output is correct
6 Correct 398 ms 136952 KB Output is correct
7 Correct 399 ms 137052 KB Output is correct