QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89113#5258. MortgageDenisovWA 2ms15912kbC++1412.1kb2023-03-19 03:23:092023-03-19 03:23:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 03:23:11]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:15912kb
  • [2023-03-19 03:23:09]
  • 提交

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=18;

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: 0
Wrong Answer
time: 2ms
memory: 15912kb

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:

stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents

result:

wrong answer 1st lines differ - expected: '10', found: 'stay with parents'