QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89134 | #5258. Mortgage | Denisov | WA | 22ms | 16964kb | C++20 | 14.0kb | 2023-03-19 04:51:26 | 2023-03-19 04:51:28 |
Judging History
answer
#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
const int max_n = 2e5+10;
const int max_log=31;
const long long inf = 4000111222000111222LL;
/*struct Line {
long double k, b;
Line(long double k, long double b): k(k), b(b) {
}
long double get_value(long double x) const {
return k * x + b;
}
bool operator < (const Line &l) const {
return k > l.k || (k == l.k && b < l.b);
}
};
long double intersection(const Line &l1, const Line &l2) {
return (l2.b - l1.b) / (l1.k - l2.k);
}*/
struct Line {
long long k, b;
Line(long long k = 0, long long b = 0): k(k), b(b) {
}
long long get_value(long long x) const {
return k * x + b;
}
bool operator < (const Line &l) const {
return k > l.k || (k == l.k && b < l.b);
}
};
long long intersection(const Line &l1, const Line &l2) {
long long a = l2.b - l1.b;
long long b = l1.k - l2.k;
return a / b - ((a ^ b) < 0 && a % b);
}
template<int x_increase>
class LineContainer {
public:
LineContainer(): pos(0) {
}
void clear() {
pos = 0;
// last_x = (x_increase == 1 ? numeric_limits<long long>::min() : numeric_limits<long long>::max());
v.clear();
}
void add(const Line &l) {
if (!v.empty()){
assert(v.back().k >= l.k);
if (v.back().k == l.k) {
if (l.b >= v.back().b) {
return;
}
v.pop_back();
}
while (v.size() >= 2 && intersection(v[v.size() - 2], v.back()) >= intersection(v.back(), l)) {
v.pop_back();
}
}
v.push_back(l);
}
long long get_min(long long x) {
if (v.empty()) {
return inf;
}
if (x_increase == 1) {
// assert(last_x <= x);
// last_x = x;
pos = min(pos, v.size() - 1);
while (pos + 1 < v.size() && v[pos].get_value(x) > v[pos + 1].get_value(x)) {
++pos;
}
return v[pos].get_value(x);
} else if (x_increase == -1) {
// assert(last_x >= x);
// last_x = x;
while (v.size() >= 2 && v.back().get_value(x) > v[v.size() - 2].get_value(x)) {
v.pop_back();
}
return v.back().get_value(x);
} else {
int l = -1, r = v.size() - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (x <= intersection(v[mid], v[mid + 1])) {
r = mid;
} else {
l = mid;
}
}
return v[r].get_value(x);
}
}
size_t pos;
// long long last_x;
vector<Line> v;
};
namespace fastio {
const int buf_size = 1 << 14, small = 30;
char buf_read[buf_size + small];
char buf_write[buf_size + small];
char *ptr_read = buf_read + buf_size;
char *ptr_write = buf_write;
long long read_int() {
#if __APPLE__
ll x;
cin>>x;
return x;
#endif
auto getChar = []() {
if (ptr_read == buf_read + buf_size){
buf_read[fread(buf_read, 1, buf_size, stdin)] = 0;
ptr_read = buf_read;
}
return *ptr_read++;
};
char c = getChar();
while (c && (c < '0' || c > '9') && c != '-') {
c = getChar();
}
long long z = 1;
if (c == '-') {
z = -1;
c = getChar();
}
long long res = 0;
while (c >= '0' && c <= '9'){
res = res * 10 + (c - '0');
c = getChar();
}
return z * res;
}
void write_flush() {
fwrite(buf_write, 1, ptr_write - buf_write, stdout);
ptr_write = buf_write;
}
void write_int(long long x) {
if (x < 0) {
*ptr_write++ = '-';
x = -x;
}
char *start = ptr_write;
if (!x) {
*ptr_write++ = '0';
}
while (x) {
*ptr_write++ = x % 10 + '0';
x /= 10;
}
reverse(start, ptr_write);
if (ptr_write >= buf_write + buf_size) {
write_flush();
}
}
void write_char(char c) {
*ptr_write++ = c;
if (ptr_write >= buf_write + buf_size) {
write_flush();
}
}
}
LineContainer<0> lc0;
LineContainer<+1> lc1;
int n,m;
ll pref[max_n];
int l[max_n];
int r[max_n];
int L[max_n];
int R[max_n];
int M[max_n];
int ans[max_n];
bool solved_req[max_n];
ll mn[max_n];
LineContainer<+1> lc1_tree[2*max_n];
//vector<int> req_vh[4*max_n];
//vector<int> on_left;
//vector<int> on_right_partially;
//vector<int> on_right_fully;
//
//void solve_mn_fast(int l1,int r1,vector<int> req)
//{
// if (l1==r1){
// for (auto i:req){
// mn[i]=min(mn[i],pref[l1]-1ll*l1*M[i]);
// }
// return;
// }
// int m1=(l1+r1)/2;
// vector<int> req_l;
// vector<int> req_r;
// on_left.clear();
// on_right_partially.clear();
// on_right_fully.clear();
// for (auto i:req){
// if (r[i]<=m1){
// req_l.pb(i);
// }
// else if (l[i]>=m1+1){
// req_r.pb(i);
// }
// else{
// req_l.pb(i);
// if (r[i]<r1){
// on_right_partially.pb(i);
// }
// else{
// on_right_fully.pb(i);
// }
// }
// }
// sort(all(on_right_partially),[&](const int& lhs,const int &rhs){
// return r[lhs]>r[rhs];
// });
// {
// lc0.clear();
// for (int j=m1+1;j<=r1;j++){
// lc0.add(Line(-j,pref[j]));
// while (!on_right_partially.empty() && r[on_right_partially.back()]==j){
// int id=on_right_partially.back();
// on_right_partially.pop_back();
// mn[id]=min(mn[id],lc0.get_min(M[id]));
// }
// }
// assert(on_right_partially.empty());
// }
// {
// lc1.clear();
// for (int j=m1+1;j<=r1;j++){
// lc1.add(Line(-j,pref[j]));
// }
// for (auto i:on_right_fully){
// mn[i]=min(mn[i],lc1.get_min(M[i]));
// }
// }
// solve_mn_fast(l1,m1,req_l);
// solve_mn_fast(m1+1,r1,req_r);
//}
void build(int v,int l,int r)
{
lc1_tree[v].v.reserve(r-l+1);
for (int i=l;i<=r;i++){
lc1_tree[v].add(Line(-i,pref[i]));
}
if (l==r){
return;
}
int m=(l+r)/2;
build(v+1,l,m);
build(v+2*(m-l+1),m+1,r);
}
//void push_req(int v,int l,int r,int tl,int tr,int id)
//{
// if (l>tr || r<tl){
// return;
// }
// if (l>=tl&&r<=tr){
// req_vh[v].pb(id);
// return;
// }
// int m=(l+r)/2;
// push_req(2*v,l,m,tl,tr,id);
// push_req(2*v+1,m+1,r,tl,tr,id);
//}
vector<int> req_on_deep[20];
void solve_mn_fast2(int v,int l1,int r1,int deep=0)
{
if (req_on_deep[deep].empty()){
return;
}
if (l1==r1){
for (auto i:req_on_deep[deep]){
mn[i]=min(mn[i],pref[l1]-1ll*l1*M[i]);
}
return;
}
int m1=(l1+r1)/2;
vector<int> left;
vector<int> right;
lc1_tree[v].pos = 0;
// lc1_tree[v].last_x = numeric_limits<long long>::min();
req_on_deep[deep+1].clear();
for (auto i:req_on_deep[deep]){
if (l[i]<=l1 && r1<=r[i]){
mn[i]=min(mn[i],lc1_tree[v].get_min(M[i]));
}
else{
if (l[i]<=m1){
req_on_deep[deep+1].pb(i);
}
}
}
solve_mn_fast2(v+1,l1,m1,deep+1);
req_on_deep[deep+1].clear();
for (auto i:req_on_deep[deep]){
if (l[i]<=l1 && r1<=r[i]){
// mn[i]=min(mn[i],lc1_tree[v].get_min(M[i]));
}
else{
if (r[i]>=m1+1){
req_on_deep[deep+1].pb(i);
}
}
}
solve_mn_fast2(v+2*(m1-l1+1),m1+1,r1,deep+1);
}
ll sub;
void get_kostya(int v, int tl, int tr, int l, int r,int id) {
LOG(v,tl,tr,l,r,id);
if (mn[id]-sub<0) return;
ll val = lc1_tree[v].get_min(M[id]);
if (val > mn[id]) return;
if (tl == l && tr == r) {
mn[id]=min(mn[id], val);
return;
}
if (val-sub>=0) return;
if (l <= -lc1_tree[v].v[lc1_tree[v].pos].k && -lc1_tree[v].v[lc1_tree[v].pos].k <= r) {
mn[id]=min(mn[id], val);
return;
}
int mid = (tl + tr) / 2;
if (r <= mid) {
get_kostya(v+1, tl, mid, l, r,id);
return;
} else if (l > mid) {
get_kostya(v + 2*(mid-tl+1), mid + 1, tr, l, r,id);
return;
}
get_kostya(v+1, tl, mid, l, mid,id);
get_kostya(v+2*(mid-tl+1), mid + 1, tr, mid + 1, r,id);
}
void solve_req(vector<int> req)
{
LOG("solve_req");
for (auto i:req){
solved_req[i]=1;
mn[i]=1e18;
}
// for (auto i:req){
// for (int j=l[i];j<=r[i];j++){
// mn[i]=min(mn[i],pref[j]-1ll*j*M[i]);
// }
// }
sort(all(req),[&](const int& lhs,const int &rhs){
return M[lhs]<M[rhs];
});
// req_on_deep[0]=req;
// solve_mn_fast2(1,0,n-1,0);
for (int i=0;i<2*max_n;i++){
lc1_tree[i].pos=0;
}
for (auto i:req){
if (l[i] - 1 >= 0) {
sub = pref[::l[i] - 1] - 1ll * (::l[i] - 1) * M[i];
}
else {
sub = +M[i];
}
get_kostya(1,0,n-1,l[i],r[i],i);
}
// solve_mn_fast(0,n-1,req);
// for (int i=0;i<4*max_n;i++){
// lc1_tree[i].pos = 0;
// lc1_tree[i].last_x = numeric_limits<long long>::min();
// sort(all(req_vh[i]),[&](const int& lhs,const int &rhs){
// return M[lhs]<M[rhs];
// });
// for (auto j:req_vh[i]){
// mn[j]=min(mn[j],lc1_tree[i].get_min(M[j]));
// }
// }
for (auto i:req){
LOG(i,M[i],mn[i]);
if (mn[i]-pref[l[i]-1]+1ll*(l[i]-1)*M[i]<0){
solved_req[i]=0;
}
}
}
/*
i,M[i],mn[i] :: 0 500000005 -3500000002
i,M[i],mn[i] :: 1 500000005 -1499999989
i,M[i],mn[i] :: 2 500000005 -1999999989
i,M[i],mn[i] :: 3 500000005 -2499999996
i,M[i],mn[i] :: 4 500000005 -4000000008
i,M[i],mn[i] :: 0 500000005 -3500000002
i,M[i],mn[i] :: 1 500000005 -1499999989
i,M[i],mn[i] :: 2 500000005 -1999999989
i,M[i],mn[i] :: 3 500000005 -2499999996
i,M[i],mn[i] :: 4 500000005 -4000000008
*/
const bool gen=0;
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (gen){
n=2e5;
m=2e5;
}
else{
n=fastio::read_int();
m=fastio::read_int();
}
for (int i=0;i<n;i++){
int a;
if (gen){
a=rand()%10000;
}
else{
a=fastio::read_int();
}
pref[i] = (i==0 ? 0 : pref[i-1]) + a;
}
build(1,0,n-1);
for (int i=0;i<m;i++){
if (gen){
l[i]=rand()%n;
r[i]=rand()%n;
if (l[i]>r[i]){
swap(l[i],r[i]);
}
}
else{
int s,k;
s=fastio::read_int();
k=fastio::read_int();
l[i]=s-1;
r[i]=s+k-2;
}
// push_req(1,0,n-1,l[i],r[i],i);
L[i]=-1;
R[i]=min(pref[l[i]] - (l[i] ? pref[l[i] - 1] : 0ll), (pref[r[i]] - (l[i] ? pref[l[i] - 1] : 0ll)) / (r - l + 1));
if (R[i] < 0) R[i] = -1;
}
for (int iter=0;iter<max_log;iter++){
vector<int> req;
for (int i=0;i<m;i++){
if (L[i]!=R[i]){
M[i]=(L[i]+R[i]+1)/2;
req.pb(i);
}
}
solve_req(req);
for (int i=0;i<m;i++){
if (L[i]!=R[i]){
if (solved_req[i]){
L[i]=M[i];
}
else{
R[i]=M[i]-1;
}
}
}
}
for (int i=0;i<m;i++){
if (L[i]==-1){
cout<<"stay with parents"<<"\n";
}
else{
cout<<L[i]<<"\n";
}
}
}
/*
9 5
6 1 10 9 5 -2 3 1 -1
3 6
1 4
3 3
6 1
8 2
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 22ms
memory: 16964kb
input:
10 10 21 18 19 18 16 15 13 13 13 10 10 1 6 4 7 3 2 2 6 5 2 6 3 2 4 1 1 5 6 3
output:
0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '10', found: '0'