QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186065 | #5669. Traveling in Jade City | aesthetic# | WA | 360ms | 34884kb | C++20 | 5.1kb | 2023-09-23 05:05:53 | 2023-09-23 05:05:54 |
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 bit[maxn];
void add(int x, int v)
{
x++;
for(; x<=m+n+2; x+=x&-x)
bit[x]+=v;
}
int pref(int x)
{
x++;
int ans=0;
for(; x>0; x-=x&-x)
ans+=bit[x];
return ans;
}
int query(int x, int y)
{
if(x > y)
swap(x, y);
// cout<<"query "<<x<<" "<<y<<endl;
return pref(y)-pref(x-1);
}
void update(int x, int v)
{
// cout<<"update "<<x<<" "<<v<<endl;
int antes=query(x, x);
add(x, v-antes);
}
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();
for(int i=1; i<=n+m+1; i++)
{
update(i, a[i]);
}
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));
mn=min(mn, query(v, n)+query(1, u-1));
}
else if(u>n && v>n)
{
mn=min(mn, 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: 5628kb
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: 5628kb
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
Wrong Answer
time: 360ms
memory: 34884kb
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...
output:
177406400 122264600 70328400 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295200 impossible 22163200 impossible impossible impossible 11422200 impossible 62579800 impossible 164661200 impossible 20157200 impossible impossible impossible impossi...
result:
wrong answer 23rd lines differ - expected: '35339400', found: '164661200'