이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
// #include "meetings.h"
using namespace std;
#define sq 320
#define maxN 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}
ll n, q;
pii p[maxN];
ll A[maxN];
ll B[maxN];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
q = L.size();
n = H.size();
vector <ll> E;
for(ll i = 0; i < n; i++) {
p[i].ss = n;
while(!E.empty() && H[E.back()] < H[i]) p[E.back()].ss = i, E.pop_back();
p[i].ff = -1;
if(!E.empty()) p[i].ff = E.back();
E.pb(i);
}
// for(int i = 0; i < n; i++) cout << p[i].ff << " " << p[i].ss << "\n";
vector <ll> ans;
for(ll i = 0; i < q; i++) {
ll mn = 2e9;
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
for(ll h = L[i]; h <= R[i]; h++) {
if(h == L[i] || H[h] >= H[h-1]) A[h] = A[p[h].ff] + (h - max(p[h].ff + 1, L[i]) + 1) * H[h];
else A[h] = A[h-1] + H[h];
}
for(ll h = R[i]; h >= L[i]; h--) {
if(h == R[i] || H[h] >= H[h+1]) B[h] = B[p[h].ss] + (min(p[h].ss - 1, R[i]) - h + 1) * H[h];
else B[h] = B[h+1] + H[h];
mn = min(mn, A[h] + B[h] - H[h]);
// cout << h << " - " << A[h] << " " << B[h] << " " << H[h] << "\n";
}
ans.pb(mn);
}
return ans;
}
// int main()
// {
// cin >> n >> q;
// ll x, y;
// vector <int> a, b, c;
// for(ll i = 1; i <= n; i++) cin >> x, a.pb(x);
// for(ll i = 1; i <= q; i++) cin >> x >> y, b.pb(x), c.pb(y);
// vector <ll> res = minimum_costs(a, b, c);
// for(auto i: res) cout << i << " ";
// }
/*
4 2
2 4 3 5
0 2
1 3
*/
컴파일 시 표준 에러 (stderr) 메시지
meetings.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
23 | #pragma GCC optimization ("O3")
|
meetings.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
24 | #pragma GCC optimization ("unroll-loops")
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |