QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186061 | #5669. Traveling in Jade City | aesthetic# | TL | 1ms | 5680kb | C++20 | 4.5kb | 2023-09-23 04:33:16 | 2023-09-23 04:33:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
typedef pair<int, int> pii;
const int inf=INT_MAX;
const int maxn=2e6+10;
int n, m, k, q;
int a[maxn];
int tree[4*maxn];
void build(int node=0, int l=1, int r=n+m+1){
if(l==r){
tree[node]=a[l];
return;
}
int mid = (l+r)/2;
build(2*node+1,l,mid);
build(2*node+2,mid+1,r);
if(tree[2*node+1]==inf)
tree[node]=inf;
else if(tree[2*node+2]==inf)
tree[node]=inf;
else
tree[node] = tree[2*node+1] + tree[2*node+2];
}
void update(int idx, int v, int node=0, int tl=1, int tr=n+m+1){
if(tl==tr){
tree[node]=v;
return;
}
int mid = (tl+tr)/2;
if(tl<=idx and idx<=mid) update(idx,v,2*node+1,tl,mid);
else update(idx,v,2*node+2,mid+1,tr);
if(tree[2*node+1]==inf)
tree[node]=inf;
else if(tree[2*node+2]==inf)
tree[node]=inf;
else
tree[node] = tree[2*node+1] + tree[2*node+2];
}
int query(int l, int r, int node=0, int tl=1, int tr=n+m+1){
if(r<tl or l>tr) return 0;
if(l<=tl and r>=tr) return tree[node];
int mid = (tl+tr)/2;
if(query(l, r, 2*node+1, tl, mid)==inf)
return inf;
else if(query(l, r, 2*node+2, mid+1, tr)==inf)
return inf;
else
return query(l, r, 2*node+1, tl, mid) + query(l, r, 2*node+2, mid+1, tr);
}
int p11(int v)
{
if(v==1)
return 0;
if(v>n)
return query(n+1, v);
return query(1, v-1);
}
int p12(int v)
{
if(v==1)
return 0;
if(v>n)
return query(n+1, v);
return query(v, n);
}
int pk1(int v)
{
if(v==k)
return 0;
if(v>n)
return query(v+1, n+m+1);
if(v<k)
return min(inf, query(k, n)+query(1, v-1));
// if(v>=k)
return query(k, v-1);
}
int pk2(int v)
{
if(v==k)
return 0;
if(v>n)
return query(v+1, n+m+1);
if(v<k)
return query(v, k-1);
// if(v>=k)
return min(inf, query(1, k-1)+query(v, n));
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ios::sync_with_stdio(0);cin.tie(0);
cin>> n>> k>> m>> q;
for(int i=1; i<=n+m+1; i++)
cin>> a[i];
int sc=0, sx=0;
for(int i=1; i<=n; i++)
sc+=a[i];
for(int i=n+1; i<=n+m+1; i++)
sx+=a[i];
build();
while(q--)
{
char c; cin>> c;
if(c=='q')
{
int u, v; cin>> u>> v;
if(u>v)
swap(u, v);
int mn=inf;
if(u<=n && v<=n)
{
mn=min(mn, query(u, v-1));
if(query(u, v)!=inf)
mn=min(mn, sc-query(u, v-1));
}
else if(u>n && v>n)
{
mn=min(mn, query(u+1, v));
if(query(u, v)!=inf)
mn=min(mn, sx-query(u+1, v));
}
mn=min(mn, p11(u)+p11(v));
mn=min(mn, p11(u)+p12(v));
mn=min(mn, p12(u)+p11(v));
mn=min(mn, p12(u)+p12(v));
mn=min(mn, pk1(u)+pk1(v));
mn=min(mn, pk1(u)+pk2(v));
mn=min(mn, pk2(u)+pk1(v));
mn=min(mn, pk2(u)+pk2(v));
mn=min(mn, p11(u)+query(n+1, n+m+1)+pk1(v));
mn=min(mn, p11(u)+query(n+1, n+m+1)+pk2(v));
mn=min(mn, p12(u)+query(n+1, n+m+1)+pk1(v));
mn=min(mn, p12(u)+query(n+1, n+m+1)+pk2(v));
mn=min(mn, pk1(u)+query(n+1, n+m+1)+p11(v));
mn=min(mn, pk1(u)+query(n+1, n+m+1)+p12(v));
mn=min(mn, pk2(u)+query(n+1, n+m+1)+p11(v));
mn=min(mn, pk2(u)+query(n+1, n+m+1)+p12(v));
if(mn==inf)
{
cout<< "impossible\n";
continue;
}
cout<< mn<< "\n";
}
else if(c=='c')
{
int i; cin>> i;
int cara=query(i, i);
if(cara==inf)
update(i, a[i]);
else
update(i, inf);
}
else if(c=='x')
{
int j; cin>> j;
j+=n+1;
int cara=query(j, j);
if(cara==inf)
update(j, a[j]);
else
update(j, inf);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5608kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #3:
score: -100
Time Limit Exceeded
input:
1000000 999999 1000000 1000000 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...