QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414785 | #6531. Base Station Construction | afy | WA | 79ms | 9600kb | C++20 | 2.8kb | 2024-05-19 18:26:29 | 2024-05-19 18:26:30 |
Judging History
answer
// Problem: C. Trading
// Contest: Codeforces - The 2023 Guangdong Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104369/problem/C
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) cerr << #x << " = " << x << endl
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
int tree[N<<2];
void update(int x,int l,int r,int p,int v){
if(l==r){
tree[x]=v;
return;
}
int mid=l+r>>1;
if(p<=mid)update(x<<1,l,mid,p,v);
else update(x<<1|1,mid+1,r,p,v);
tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
int query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[x];
}
int res=1e9;
int mid=l+r>>1;
if(ql<=mid)res=min(res,query(x<<1,l,mid,ql,qr));
if(qr>mid)res=min(res,query(x<<1|1,mid+1,r,ql,qr));
return res;
}
ll inf=1e18;
void clear(int x,int l,int r){
if(l==r){
tree[x]=inf;
return;
}
int mid=l+r>>1;
clear(x<<1,l,mid);
clear(x<<1|1,mid+1,r);
}
void solve(){
int n;
cin>>n;
n++;
clear(1,1,n);
vector<int>a(n+1);
for(int i=1;i<n;i++)cin>>a[i];
a[n]=0;
int m;
cin>>m;
vector<pair<int,int>>l(m);
for(int i=0;i<m;i++){
cin>>l[i].first>>l[i].second;
}
sort(l.begin(),l.end(),[&](auto x,auto y){
if(x.second==y.second)return x.first<y.first;
else return x.second<y.second;
});
vector<int>lst(n+1);
int j=-1;
int mn=0;
int k=-1;
for(int i=1;i<=n;i++){
while(j+1<m&&l[j+1].second<i){
j++;
if(l[j].first>=mn){
mn=l[j].first;
k=j;
}
}
lst[i]=k;
// cerr<<mn<<"\n"<<j<<"\n";
}
// for(int i=1;i<=n;i++)cerr<<lst[i]<<" ";
// cerr<<"\n";
vector<int>dp(n+1);
for(int i=1;i<=n;i++){
j=lst[i];
if(j==-1)dp[i]=a[i];
else dp[i]=query(1,1,n,l[j].first,l[j].second)+a[i];
// cerr<<i<<" "<<j<<" "<<dp[i]<< "!\n";
update(1,1,n,i,dp[i]);
// cerr<<"^^\n";
}
// cerr<<"!!!!!!";
cout<<dp[n]<<"\n";
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//freopen("debug.txt", "w", stderr);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
input:
2 5 3 2 4 1 100 3 1 3 2 4 5 5 5 7 3 4 2 2 3 1 4 2 3 4 5
output:
102 5
result:
ok 2 number(s): "102 5"
Test #2:
score: -100
Wrong Answer
time: 79ms
memory: 9600kb
input:
6201 12 88 78 46 95 84 98 55 3 68 42 6 18 19 6 9 10 11 12 12 8 11 8 12 2 3 2 3 1 5 9 9 7 8 6 11 2 4 12 12 2 4 2 9 7 10 8 8 1 7 6 11 5 76 27 48 66 61 2 1 4 3 5 8 64 81 20 6 86 9 4 55 1 7 7 9 1 43 18 81 11 22 9 61 83 14 5 6 2 6 5 8 1 4 9 9 9 9 7 7 2 5 8 9 5 6 4 8 5 8 9 9 6 6 10 66 41 84 7 80 31 22 96 ...
output:
141 48 4 126 303 141 23 170 159 139 153 194 136 89 230 93 287 89 124 130 148 27 1 193 194 93 239 303 236 150 177 57 46 18 24 66 83 160 108 62 35 122 156 81 115 138 54 242 126 28 171 86 311 244 262 87 302 81 86 173 30 129 75 91 90 179 81 224 142 154 77 111 194 247 211 53 66 17 213 101 308 137 177 24 ...
result:
wrong answer 1501st numbers differ - expected: '2892330597', found: '1000000000'