oj.uz

Submission #17622

# Submission time Handle Problem Language Result Execution time Memory
17622 2016-01-03T13:18:45 Z gs14004 Adriatic (CEOI13_adriatic) C++14
25 / 100
 2000 ms 28184 KB 
#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 cx, cy;
int getsum(int sx, int ex, int sy, int ey){
	int ret = arr[ex][ey] - arr[sx-1][ey] - arr[ex][sy-1] + arr[sx-1][sy-1];
	return ret;
}

void contract2(int &x, int &y){
	int rx = x, ry = y;
	for(int i=0; i<n; i++){
		if(x < a[i].first){
			ry = max(ry, a[i].second);
		}
		if(y > a[i].second){
			rx = min(rx, a[i].first);
		}
	}
	x = rx, y = ry;
}

void contract1(int &x, int &y){
	int rx = x, ry = y;
	for(int i=0; i<n; i++){
		if(x > a[i].first){
			ry = min(ry, a[i].second);
		}
		if(y < a[i].second){
			rx = max(rx, a[i].first);
		}
	}
	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]++;
	}
	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];
		tie(cx, cy) = 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);
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28184 KB Output is correct
2 Correct 35 ms 28184 KB Output is correct
3 Correct 31 ms 28184 KB Output is correct
4 Correct 34 ms 28184 KB Output is correct
5 Correct 31 ms 28184 KB Output is correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 28184 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 28184 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 28184 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 28180 KB Program timed out
2 Halted 0 ms 0 KB -