QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153814 | #6326. Make Convex Sequence | aesthetic | WA | 36ms | 13180kb | C++14 | 2.7kb | 2023-08-31 03:01:04 | 2023-08-31 03:01:05 |
Judging History
answer
#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#define int long long
#define dbg_loc() cerr << __PRETTY_FUNCTION__ << " : " << __LINE__ << "\n"
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v){
os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}';
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
cerr << ' ' << H;
dbg_out(T...);
}
#define LOCAL
#define LOCAL
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
///CUIDADO COM MAXN
#define N 1000010 // 1E6
int n, m, q, k, v[N];
pii w[N];
int L[N],R[N];
int cross(pii O, pii A, pii B){
return (A.f-O.f)*(B.s-O.s) - (A.s-O.s)*(B.f-O.f);
}
void solve_case(){
cin>>n;
vector<pii> caras;
rep(i,1,n+1) cin>>L[i];
vector<pii> pilha; int t=0;
rep(i,1,n+1){
cin>>R[i];
while(sz(pilha) >= 2 and cross(pilha[t-1],{i,R[i]}, pilha[t-2]) < 0) pilha.pop_back(),--t;
pilha.pb({i,R[i]});
++t;
}
vi delta(n+1);
rep(i,1,n+1){
auto it = upper_bound(all(pilha), pii(i,0)); // primeira posicao >= i
if( (*it).f == i){
continue;
}
else{
auto old = prev(it);
pii a = *old, b = *it;
double slope = (b.s - a.s)/(b.f - a.f);
double y = slope*(i-a.f) + a.s;
if(y < L[i]){
cout<<"No\n";
return;
}
}
}
cout<<"Yes\n";
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
int test_case=1;
// cin>>test_case;
while(test_case--){
solve_case();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5516kb
input:
4 2 1 2 5 4 6 5 8
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 5496kb
input:
3 1 4 2 3 7 4
output:
No
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 36ms
memory: 13180kb
input:
271757 150678576 28436211 82026915 150751377 329329758 207446456 449759844 245730845 425844298 93416110 220240900 414108016 268705922 158510126 362264528 715921 468258085 104286815 63874786 73971103 476243636 89261247 440888454 422989962 422041006 436065809 498263669 368104872 458751340 280953952 40...
output:
Yes
result:
wrong answer expected NO, found YES