Editorial for PERIOD


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstdio>
#include<limits>
#include<queue>
using namespace std;

const int N = 5000000;
long long a[2 * N];
int original[N];
int n, p, q, m, delta;

long long brute() {
    long long res = numeric_limits<long long>::max();
    for(int i = 0; i < n; ++i) {
        long long cost = numeric_limits<long long>::min();
        for(int j = 0; j < n; ++j)
            cost = max(cost, original[(i + j) % n] + (j + 1LL) * delta);
        res = min(res, cost);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> delta >> p >> q >> m;
    for(int i = 0; i < n; ++i)
        a[i] = original[i] = p * (i + 1LL) % m + q;
    copy(a, a + n, a + n);
    for(int i = 0; i < 2 * n; ++i)
        a[i] += (i + 1LL) * delta;
    deque<int> q;
    long long res = numeric_limits<long long>::max();
    for(int i = 0; i < 2 * n; ++i) {
        while(!q.empty() && a[i] >= a[q.back()]) q.pop_back();
        while(!q.empty() && q.front() <= i - n) q.pop_front();
        q.push_back(i);
        if(i >= n - 1)
            res = min(res, a[q.front()] - 1LL * (i - n + 1) * delta);
    }
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

program periodnb;
uses    math;
const   fi='';
        maxN=10000007;
type    e=record
        val:int64;
        pos,carry:longint;
        end;
var     a,timer:array[-1..maxN] of int64;
        stack:array[-1..maxN] of e;
        n,head,tail:longint;
        p,q,m,time,res:int64;

procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n,time);
        readln(f,p,q,m);
        close(f);
end;

procedure init;
var     i:longint;
        t,pp:int64;
begin
        pp:=0;
        p:=p mod m;
        for i:=1 to n do
        begin
                pp:=pp+p;
                while pp>=m do pp:=pp-m;
                a[i]:=pp + q;
        end;
        for i:=n+1 to n shl 1 do
        a[i]:=a[i-n];
        timer[0]:=0;
        for i:=1 to n shl 1 do
        timer[i]:=timer[i-1]+time;
        for i:=1 to n do
               a[i]:=a[i]+timer[i];
        head:=1;tail:=0;
        res:=high(int64);
end;

procedure process;
var     i:longint;
begin
        for i:=1 to n do
        begin
                while (head<=tail) and (stack[tail].val<=a[i]) do dec(tail);
                inc(tail);
                stack[tail].val:=a[i];
                stack[tail].pos:=i;
                stack[tail].carry:=0;
        end;
        for i:=n+1 to n shl 1 do
        begin
                inc(stack[tail].carry);
                if head<>tail then
                inc(stack[head].carry);
                while (head<=tail) and (stack[head].pos<=(i-n)) do
                begin
                        inc(Head);
                        if head<>tail then
                        inc(stack[head].carry,stack[head-1].carry);
                end;
                a[i]:=a[i]+timer[n];
                while (head<=tail) and ((stack[tail].val-timer[stack[Tail].carry])<=a[i]) do
                begin
                        dec(tail);
                        if head<tail then
                        inc(stack[tail].carry,stack[tail+1].carry);
                end;
                inc(tail);
                stack[tail].val:=a[i];
                stack[tail].pos:=i;
                stack[tail].carry:=0;
                res:=min(res,stack[head].val-timer[stack[Head].carry]);
        end;
end;

begin
        input;
        init;
        process;
        write(res);
end.

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<iostream>
#define MAX   5000500
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
using namespace std;
typedef long long ll;
ll a[MAX];
ll maxleft[MAX];
ll maxright[MAX];
int n;
ll d;
void init(void) {
    ll p,m,q;   
    cin >> n;
    cin >> d;
    cin >> p >> q >> m;
    FOR(i,1,n) a[i]=(p*i)%m+q+d*i;  
    FOR(i,1,n) maxleft[i]=max(maxleft[i-1],a[i]);
    FORD(i,n,1) maxright[i]=max(maxright[i+1],a[i]);
}
void process(void) {
    ll res;
    ll tmp=0;
    FOR(i,1,n) tmp=max(tmp,a[i]);
    res=tmp;
    FOR(i,1,n-1) {
        tmp=max(maxleft[i]+d*(n-i),maxright[i+1]-d*i);
        res=min(res,tmp);
    }
    cout << res;
}
int main(void) {
    //freopen("PERIOD.INP","r",stdin);
    //freopen("PERIOD.OUT","w",stdout);
    init();
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.