Submission #1546983


Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define fio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
// #define y1 asdf__y1;

const int N = 2e5+5;
pii P[N];
int X1,X2,Y1,Y2,n;

vector<pii> ir;
set<int> cc;
map<int,int> lab;
int A[N];

int lis(int *A, int n) {
	if(n==0) return 0;
	vector<int> v = {0}; //contains indices of lis by the end
	for(int i = 1; i < n; ++i) {
		if(A[i] > A[v.back()])
			v.push_back(i);
		else {
			int lo = 0, hi = v.size()-1;
			while(hi-lo>1) {
				int md = (lo+hi)/2;
				((A[i] > A[v[md]])?lo:hi) = md;
			}
			v[hi] = A[v[hi]]<A[i]?v[hi]:i;
			// v[hi] = min(v[h]i;
		}
	}
	return v.size();
}

int B[N];

const bool dbg = 0;

int main() {	
	scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
	scanf("%d",&n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d",&P[i].fi,&P[i].se);
	if(X1 > X2) {
		X1 = -X1, X2 = -X2;
		for(pii &p : P)
			p.fi = -p.fi;
	}
	if(Y1 > Y2) {
		Y1 = -Y1, Y2 = -Y2;
		for(pii &p : P)
			p.se = -p.se;
	}
	for(int i = 0; i < n; ++i) {
		pii p = P[i];
		if(X1 <= p.fi && p.fi <= X2 && Y1 <= p.se && p.se <= Y2)
			ir.pb(p);
	}
	sort(ir.begin(),ir.end());
	n = ir.size();
	for(int i = 0; i < n; ++i)
		B[i] = ir[i].se;
	int ans = lis(B,n);
	long double pi = 2*acosl(0);
	long double ra = (long double)(Y2-Y1 + X2-X1) * 100.0;
	if(ans == Y2-Y1+1 || ans == X2-X1+1) {
		ra += 10*pi-20;
		--ans;
		if(dbg) cout << "1 bad\n";
	}
	ra += (5*pi-20) * ans;
	if(dbg) cout << ans << " good\n";
	printf("%.20lf\n",double(ra));
}

Submission Info

Submission Time
Task C - Fountain Walk
User cephian
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1684 Byte
Status WA
Exec Time 68 ms
Memory 6000 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
                                   ^
./Main.cpp:47:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:49:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&P[i].fi,&P[i].se);
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 40
WA × 7
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 2 ms 1792 KB
sample_03.txt AC 2 ms 1792 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 2 ms 1792 KB
subtask_1_03.txt AC 2 ms 1792 KB
subtask_1_04.txt AC 2 ms 1792 KB
subtask_1_05.txt AC 2 ms 1792 KB
subtask_1_06.txt AC 2 ms 1792 KB
subtask_1_07.txt AC 2 ms 1792 KB
subtask_1_08.txt AC 2 ms 1792 KB
subtask_1_09.txt AC 15 ms 768 KB
subtask_1_10.txt AC 30 ms 1792 KB
subtask_1_11.txt AC 8 ms 512 KB
subtask_1_12.txt AC 58 ms 6000 KB
subtask_1_13.txt AC 32 ms 1792 KB
subtask_1_14.txt AC 16 ms 1792 KB
subtask_1_15.txt AC 8 ms 512 KB
subtask_1_16.txt AC 58 ms 6000 KB
subtask_1_17.txt AC 26 ms 1792 KB
subtask_1_18.txt AC 21 ms 1792 KB
subtask_1_19.txt AC 21 ms 1792 KB
subtask_1_20.txt AC 55 ms 6000 KB
subtask_1_21.txt AC 58 ms 6000 KB
subtask_1_22.txt AC 58 ms 6000 KB
subtask_1_23.txt AC 58 ms 6000 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB
subtask_1_28.txt WA 38 ms 1920 KB
subtask_1_29.txt WA 40 ms 1920 KB
subtask_1_30.txt WA 68 ms 4336 KB
subtask_1_31.txt AC 41 ms 4336 KB
subtask_1_32.txt AC 41 ms 6000 KB
subtask_1_33.txt AC 50 ms 5104 KB
subtask_1_34.txt AC 49 ms 4336 KB
subtask_1_35.txt WA 60 ms 4336 KB
subtask_1_36.txt WA 56 ms 4336 KB
subtask_1_37.txt AC 52 ms 5744 KB
subtask_1_38.txt WA 56 ms 5104 KB
subtask_1_39.txt WA 59 ms 4976 KB
subtask_1_40.txt AC 55 ms 5104 KB
subtask_1_41.txt AC 46 ms 5104 KB