Submission #170636

#	Time	Username	Problem	Language	Result	Execution time	Memory
170636		jacynkaa	Adriatic (CEOI13_adriatic)	C++17	100 / 100	404 ms	137108 KiB

adriatic

#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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20