Submission #17629

#TimeUsernameProblemLanguageResultExecution timeMemory
17629gs14004Adriatic (CEOI13_adriatic)C++14
60 / 100
2000 ms28224 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <bitset> #include <iostream> using namespace std; typedef long long lint; typedef long double llf; typedef pair<int, int> pi; const int S = 2500; int n, arr[2505][2505]; pi a[250005]; int getsum(int sx, int ex, int sy, int ey){ return arr[ex][ey] - arr[sx-1][ey] - arr[ex][sy-1] + arr[sx-1][sy-1]; } int prec1[2505], prec2[2505], prec3[2505], prec4[2505]; void contract1(int &x, int &y){ int rx = max(x, prec2[y+1]), ry = min(y, prec1[x-1]); x = rx, y = ry; } void contract2(int &x, int &y){ int rx = min(x, prec4[y-1]), ry = max(y, prec3[x+1]); x = rx, y = ry; } int main(){ scanf("%d",&n); for(int i=0; i<n; i++){ scanf("%d %d",&a[i].first, &a[i].second); arr[a[i].first][a[i].second]++; } memset(prec1, 0x3f, sizeof(prec1)); memset(prec4, 0x3f, sizeof(prec4)); for(int i=0; i<n; i++){ prec1[a[i].first] = min(prec1[a[i].first], a[i].second); prec2[a[i].second] = max(prec2[a[i].second], a[i].first); prec3[a[i].first] = max(prec3[a[i].first], a[i].second); prec4[a[i].second] = min(prec4[a[i].second], a[i].first); } for(int i=1; i<=S; i++){ prec1[i] = min(prec1[i-1], prec1[i]); prec2[S+1-i] = max(prec2[S+1-i], prec2[S+2-i]); prec3[S+1-i] = max(prec3[S+1-i], prec3[S+2-i]); prec4[i] = min(prec4[i-1], prec4[i]); } for(int i=1; i<=S; i++){ for(int j=1; j<=S; j++){ arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1]; } } for(int i=0; i<n; i++){ int x1, y1, x2, y2; tie(x1, y1) = a[i], tie(x2, y2) = a[i]; lint ret = n - 3; for(int t=0; t<n; t++){ ret += getsum(x1, S, 1, y1) + getsum(1, x2, y2, S); contract1(x1, y1); contract2(x2, y2); } printf("%lld\n",ret); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...