oj.uz

Submission #61872

# Submission time Handle Problem Language Result Execution time Memory
61872 2018-07-27T03:29:08 Z Benq Adriatic (CEOI13_adriatic) C++11
100 / 100
 435 ms 144600 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2501;

template<class T, int SZ> struct sums {
    T sum[SZ][SZ];
    T maxX[SZ+1], maxY[SZ+1];
    T minX[SZ+1], minY[SZ+1];
    sums () { memset(sum,0,sizeof sum); }
    void init() {
        F0R(i,SZ+1) minX[i] = minY[i] = SZ;
        FOR(i,1,SZ) FOR(j,1,SZ) {
            if (sum[i][j]) {
                maxX[j] = max(maxX[j],i);
                maxY[i] = max(maxY[i],j);
                minX[j] = min(minX[j],i);
                minY[i] = min(minY[i],j);
            }
            sum[i][j] += sum[i][j-1]
            +sum[i-1][j]-sum[i-1][j-1];
        }
        FOR(i,1,SZ) {
            minY[i] = min(minY[i],minY[i-1]);
            minX[i] = min(minX[i],minX[i-1]);
        }
        FORd(i,1,SZ) {
            maxX[i] = max(maxX[i],maxX[i+1]);
            maxY[i] = max(maxY[i],maxY[i+1]);
        }
    }
    T get(int X1, int X2, int Y1, int Y2) {
        return sum[X2][Y2]-sum[X1-1][Y2]
        	-sum[X2][Y1-1]+sum[X1-1][Y1-1];
    }
};

sums<int,MX> S;

int N;
ll dp[2][MX][MX];
pi p[250001];

void gendp0() {
    FORd(i,1,MX) FOR(j,1,MX) { // currently have all points such that x < i or y > j
        dp[0][i][j] = S.get(i,MX-1,1,j);
        if (!dp[0][i][j]) continue;
        dp[0][i][j] += dp[0][max(i,S.maxX[j+1])][min(j,S.minY[i-1])];
    }
}

void gendp1() {
    FOR(i,1,MX) FORd(j,1,MX) {
        dp[1][i][j] = S.get(1,i,j,MX-1);
        if (!dp[1][i][j]) continue;
        dp[1][i][j] += dp[1][min(i,S.minX[j-1])][max(j,S.maxY[i+1])];
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N) {
        cin >> p[i].f >> p[i].s;
        S.sum[p[i].f][p[i].s] ++;
    }
    S.init();
    gendp0();
    gendp1();
    
    F0R(i,N) cout << dp[0][p[i].f][p[i].s]+dp[1][p[i].f][p[i].s]+N-3 << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 122744 KB Output is correct
2 Correct 155 ms 122944 KB Output is correct
3 Correct 156 ms 122944 KB Output is correct
4 Correct 141 ms 122944 KB Output is correct
5 Correct 190 ms 122944 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 122944 KB Output is correct
2 Correct 180 ms 123020 KB Output is correct
3 Correct 164 ms 123260 KB Output is correct
4 Correct 158 ms 123260 KB Output is correct
5 Correct 185 ms 123260 KB Output is correct
6 Correct 180 ms 123260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 123296 KB Output is correct
2 Correct 177 ms 123424 KB Output is correct
3 Correct 168 ms 123424 KB Output is correct
4 Correct 162 ms 123604 KB Output is correct
5 Correct 160 ms 123624 KB Output is correct
6 Correct 195 ms 123820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 124160 KB Output is correct
2 Correct 169 ms 124316 KB Output is correct
3 Correct 208 ms 124648 KB Output is correct
4 Correct 194 ms 124724 KB Output is correct
5 Correct 177 ms 125088 KB Output is correct
6 Correct 211 ms 125468 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 131132 KB Output is correct
2 Correct 385 ms 133044 KB Output is correct
3 Correct 435 ms 135416 KB Output is correct
4 Correct 358 ms 137168 KB Output is correct
5 Correct 375 ms 139660 KB Output is correct
6 Correct 385 ms 142108 KB Output is correct
7 Correct 311 ms 144600 KB Output is correct