oj.uz

답안 #72516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72516 2018-08-26T08:43:50 Z IDxTree(#2155, TAMREF, imeimi2000, Diuven) 오르막길 (FXCUP3_hill) C++17
100 / 100
 1253 ms 41484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf=2e9, MX=300010;

struct edge{
	ll x=1, y=0;
	bool operator > (const edge &e) const {
		return y*e.x>e.y*x;
	}
	bool operator == (const edge &e) const {
		return y*e.x==e.y*x;
	}
};

struct node1{
	int idx; edge e;
	bool operator < (const node1 &nd) const {
		return idx<nd.idx;
	}
};

struct node2{
	int idx; edge e;
	bool operator < (const node2 &nd) const {
		return nd.e>e || (e==nd.e && idx<nd.idx);
	}
	bool operator==(const node2 &nd) const {
        return !(*this < nd) && !(nd < *this);
	}
};

set<node1> S1;

struct pq {
    priority_queue<node2> pq1, pq2;
    void insert(node2 x) {
        pq1.push(x);
    }
    void erase(node2 x) {
        pq2.push(x);
        while (!pq2.empty() && pq1.top() == pq2.top()) {
            pq1.pop();
            pq2.pop();
        }
    }
    node2 get() const {
        return pq1.top();
    }
} S2;


int n;
ll X[MX], Y[MX];
ll c;

int gcd(int x, int y){
	if(y==0) return x;
	return gcd(y,x%y);
}

ll area(int l, int r){
	return (X[r]-X[l])*(Y[l]+Y[r]);
}

int main(){
scanf("%d%lld", &n, &c);	
c*=2;
	for(int i=1; i<=n; i++) scanf("%lld", &X[i]);
	for(int i=1; i<=n; i++) scanf("%lld", &Y[i]);
	for(int i=1; i<n; i++){
		edge e;
		e.x=X[i+1]-X[i];
		e.y=Y[i+1]-Y[i];
		S1.insert({i,e});
		S2.insert({i,e});
	}
	while(true){
		node2 a=S2.get();
		int i=a.idx; edge e=a.e;
		if(i==1) break;

		node1 b=*prev(S1.find({i,e}));
		int j=b.idx; edge f=b.e;

		int k=n;

		auto it=S1.find({i,e});
		auto it2 = next(it);
		if(it2!=S1.end()) k=it2->idx;

		ll now=area(j,k)-area(j,i)-area(i,k);

		if(now>c) break;

//		cout<<"POINTS: "<<j<<' '<<i<<' '<<k<<'\n';

		c-=now;

		S1.erase({i,e}), S2.erase({i,e});
		S1.erase({j,f}), S2.erase({j,f});

		edge g; g.x=e.x+f.x, g.y=e.y+f.y;
		S1.insert({j,g}), S2.insert({j,g});
//		cout<<S1.size()<<", "<<S2.size()<<'\n';
	}
	{
		edge ans=S2.get().e;
		int x=ans.x, y=ans.y, g=gcd(x,y);
printf("%d/%d\n", y/g,x/g);
	}
	return 0;
}

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:68:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%lld", &n, &c); 
 ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", &X[i]);
                          ~~~~~^~~~~~~~~~~~~~~
hill.cpp:71:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", &Y[i]);
                          ~~~~~^~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 2 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 3 ms 776 KB Output is correct
8 Correct 3 ms 776 KB Output is correct

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 2 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 3 ms 776 KB Output is correct
8 Correct 3 ms 776 KB Output is correct
9 Correct 280 ms 34012 KB Output is correct
10 Correct 225 ms 34012 KB Output is correct
11 Correct 1253 ms 41484 KB Output is correct
12 Correct 419 ms 41484 KB Output is correct
13 Correct 152 ms 41484 KB Output is correct
14 Correct 254 ms 41484 KB Output is correct
15 Correct 444 ms 41484 KB Output is correct
16 Correct 270 ms 41484 KB Output is correct
17 Correct 339 ms 41484 KB Output is correct
18 Correct 182 ms 41484 KB Output is correct
19 Correct 274 ms 41484 KB Output is correct