oj.uz

Submission #573399

# Submission time Handle Problem Language Result Execution time Memory
573399 2022-06-06T14:19:37 Z DJ035 Adriatic (CEOI13_adriatic) C++17
100 / 100
 218 ms 158700 KB 
#include <bits/stdc++.h>
#define MEM 2555
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
#define sz size()
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e18+7;
const ll MOD = 1e9+7;
ll MX = 2500;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}

string s;
ll n;
ll a[MEM][MEM];
pi b[252525];
ll cn[MEM], cx[MEM], dn[MEM], dx[MEM];
ll dp[MEM][MEM], dp2[MEM][MEM];
ll sum(ll sx, ll ex, ll sy, ll ey){
	return a[ex][ey]-a[sx-1][ey]-a[ex][sy-1]+a[sx-1][sy-1];
}
signed main(){
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> b[i].x >> b[i].y;
        a[b[i].x][b[i].y]++;
    }
    memset(cn, 0x3f, sizeof(cn));
    memset(dn, 0x3f, sizeof(dn));
    //cout << 'd';
    for(int i=1; i<=n; i++){
        cn[b[i].x] = min(cn[b[i].x], b[i].y);
        cx[b[i].y] = max(cx[b[i].y], b[i].x);
        dx[b[i].x] = max(dx[b[i].x], b[i].y);
        dn[b[i].y] = min(dn[b[i].y], b[i].x);
    }
    //cout << 'd';
    for(int i=1; i<=MX; i++){
        cn[i] = min(cn[i], cn[i-1]);
        dn[i] = min(dn[i], dn[i-1]);
        cx[MX-i+1] = max(cx[MX-i+1], cx[MX-i+2]);
        dx[MX-i+1] = max(dx[MX-i+1], dx[MX-i+2]);
    }
    //cout << 'd';
    for(int i=1; i<=MX; i++){
        for(int j=1; j<=MX; j++){
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    //cout << 'd';
    ll r,c;
    for(ll i=MX; i; i--){
        for(ll j=1; j<=MX; j++){
            r=max(cx[j+1], i), c=min(cn[i-1], j);
            dp[i][j] = dp[r][c]+sum(i,MX,1LL,j);
        }
    }
    //cout << 'd';
    for(ll i=1; i<=MX; i++){
        for(ll j=MX; j; j--){
            r=min(dn[j-1], i), c=max(dx[i+1], j);
            dp2[i][j] = dp2[r][c]+sum(1LL,i,j,MX);
        }
    }
    //cout << 'd';
    for(int i=1; i<=n; i++){
        cout << dp[b[i].x][b[i].y]+dp2[b[i].x][b[i].y]+n-3 << '\n';
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 150344 KB Output is correct
2 Correct 99 ms 150368 KB Output is correct
3 Correct 110 ms 150344 KB Output is correct
4 Correct 109 ms 150368 KB Output is correct
5 Correct 123 ms 150384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 150472 KB Output is correct
2 Correct 100 ms 150376 KB Output is correct
3 Correct 118 ms 150340 KB Output is correct
4 Correct 114 ms 150336 KB Output is correct
5 Correct 102 ms 150404 KB Output is correct
6 Correct 101 ms 150376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 150504 KB Output is correct
2 Correct 103 ms 150528 KB Output is correct
3 Correct 104 ms 150488 KB Output is correct
4 Correct 97 ms 150504 KB Output is correct
5 Correct 99 ms 150544 KB Output is correct
6 Correct 133 ms 150504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 150976 KB Output is correct
2 Correct 113 ms 151072 KB Output is correct
3 Correct 127 ms 151148 KB Output is correct
4 Correct 105 ms 151032 KB Output is correct
5 Correct 107 ms 151144 KB Output is correct
6 Correct 134 ms 151192 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 156292 KB Output is correct
2 Correct 202 ms 158408 KB Output is correct
3 Correct 208 ms 158296 KB Output is correct
4 Correct 200 ms 157972 KB Output is correct
5 Correct 175 ms 158480 KB Output is correct
6 Correct 204 ms 158472 KB Output is correct
7 Correct 218 ms 158700 KB Output is correct