QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89112 | #5258. Mortgage | Denisov | WA | 20ms | 18212kb | C++14 | 12.1kb | 2023-03-19 03:21:49 | 2023-03-19 03:21:51 |
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);
//}
void solve_mn_fast2(int v,int l1,int r1,vector<int> &req)
{
if (l1==r1 || req.empty()){
for (auto i:req){
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();
for (auto i:req){
if (r[i] < l1 || r1 < l[i]) continue;
if (l[i]<=l1 && r1<=r[i]){
mn[i]=min(mn[i],lc1_tree[v].get_min(M[i]));
}
else {
if (l[i]<=m1){
left.pb(i);
}
if (r[i]>=m1+1){
right.pb(i);
}
}
}
solve_mn_fast2(v+1,l1,m1,left);
solve_mn_fast2(v+2*(m1-l1+1),m1+1,r1,right);
}
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];
});*/
solve_mn_fast2(1,0,n-1,req);
// 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
*/
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n=fastio::read_int();
m=fastio::read_int();
for (int i=0;i<n;i++){
int a;
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++){
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]=1e9+10;
}
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: 100
Accepted
time: 10ms
memory: 15984kb
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:
10 13 13 18 12 16 18 18 18 13
result:
ok 10 lines
Test #2:
score: -100
Wrong Answer
time: 20ms
memory: 18212kb
input:
1000 1000 196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...
output:
158 16 110 64 160 118 169 63 172 128 93 82 118 119 86 32 174 145 139 84 149 120 133 155 108 110 65 178 90 99 118 91 133 85 151 76 130 50 91 99 95 78 110 87 119 141 68 81 172 82 112 139 136 81 79 16 51 31 104 116 108 38 75 176 156 55 165 112 146 74 68 172 112 157 94 177 111 166 110 112 98 155 109 155...
result:
wrong answer 109th lines differ - expected: '112', found: '113'