QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#219851 | #5669. Traveling in Jade City | ZIhan# | WA | 290ms | 36228kb | C++20 | 5.3kb | 2023-10-19 19:09:27 | 2023-10-19 19:09:27 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IO ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
struct BIT{
vector<int>bit;
int n;
void init(int nn){
n=nn+1;
bit=vector<int>(n,0);
}
int lowbit(int x){return x&-x;}
int query(int x){
int res=0;
for(;x>0;x-=lowbit(x)){
res+=bit[x];
}
return res;
}
void upd(int x,int v){
for(;x<n;x+=lowbit(x)){
bit[x]+=v;
}
}
}bit,ch;
bool broke[2000060];
bool check(int l,int r){
if(l==1){
return ch.query(r)==0;
}else {
return ch.query(r)-ch.query(l-1)==0;
}
}
int qq(int l,int r){
if(l==1){
return bit.query(r);
}else {
return bit.query(r)-bit.query(l-1);
}
}
signed main(){
IO
int n,k,m,q;
cin>>n>>k>>m>>q;
memset(broke,0,sizeof(broke));
bit.init(n+m+1+5);
ch.init(n+m+1+5);
for(int i=1;i<=n;i++){
int now;
cin>>now;
bit.upd(i,now);
}
for(int i=n+1;i<=n+m+1;i++){
int now;
cin>>now;
bit.upd(i,now);
}
while(q--){
char c;
cin>>c;
if(c=='q'){
int x,y;
cin>>x>>y;
int ans=1e16;
if(x>y)swap(x,y);
if(x==1&&y==k){
//right 1~k-1
if(check(1,k-1)){
ans=min(ans,qq(1,k-1));
}
//straight
if(check(n+1,n+1+m)){
ans=min(ans,qq(n+1,n+1+m));
}
//left
if(check(k,n)){
ans=min(ans,qq(k,n));
}
}else {
int x1=1e16;//x->1
int xk=1e16;//x->k
int y1=1e16;//y->1
int yk=1e16;//y->k
int ok=1e16;//o->k
if(x==1){
x1=0;
if(check(1,k-1))xk=min(xk,qq(1,k-1));
if(check(k,n))xk=min(xk,qq(k,n));
if(check(n+1,n+m+1))xk=min(xk,qq(n+1,n+m+1));
}else if(x==k){
xk=0;
if(check(1,k-1))x1=min(x1,qq(1,k-1));
if(check(k,n))x1=min(x1,qq(k,n));
if(check(n+1,n+m+1))x1=min(x1,qq(n+1,n+m+1));
}else {
if(x>1&&x<k){
if(check(1,x-1))x1=min(x1,qq(1,x-1));
if(check(x,k-1))xk=min(xk,qq(x,k-1));
}else if(x<=n){
if(check(x,n))x1=min(x1,qq(x,n));
if(check(k,x-1))xk=min(xk,qq(k,x-1));
}else {
if(check(n+1,x))x1=min(x1,qq(n+1,x));
if(check(x+1,n+m+1))xk=min(xk,qq(x+1,n+m+1));
}
}
if(y==1){
y1=0;
if(check(1,k-1))yk=min(yk,qq(1,k-1));
if(check(k,n))yk=min(yk,qq(k,n));
if(check(n+1,n+m+1))yk=min(yk,qq(n+1,n+m+1));
}else if(y==k){
yk=0;
if(check(1,k-1))y1=min(y1,qq(1,k-1));
if(check(k,n))y1=min(y1,qq(k,n));
if(check(n+1,n+m+1))y1=min(y1,qq(n+1,n+m+1));
}else {
if(y>1&&y<k){
if(check(1,y-1))y1=min(y1,qq(1,y-1));
if(check(y,k-1))yk=min(yk,qq(y,k-1));
}else if(y<=n){
if(check(y,n))y1=min(y1,qq(y,n));
if(check(k,y-1))yk=min(yk,qq(k,y-1));
}else {
if(check(n+1,y))y1=min(y1,qq(n+1,y));
if(check(y+1,n+m+1))yk=min(yk,qq(y+1,n+m+1));
}
}
if(check(1,k-1))ok=min(ok,qq(1,k-1));
if(check(k,n))ok=min(ok,qq(k,n));
if(check(n+1,n+m+1))ok=min(ok,qq(n+1,n+m+1));
ans=min(ans,x1+y1);
ans=min(ans,xk+yk);
ans=min(ans,x1+ok+yk);
ans=min(ans,xk+ok+y1);
if(1<x&&x<k&&y<1&&y<k){
if(check(x,y-1))ans=min(ans,qq(x,y-1));
}
else if(k<x&&x<=n&&k<y&&y<=n){
if(check(x,y-1))ans=min(ans,qq(x,y-1));
}
else if(n<x&&n<y){
if(check(x+1,y))ans=min(ans,qq(x+1,y));
}
}
if(ans==1e16){
cout<<"impossible"<<endl;
}else cout<<ans<<endl;
}else if(c=='x'){
int now;
cin>>now;
now+=n+1;
if(broke[now]){
broke[now]=0;
ch.upd(now,-1);
}else {
broke[now]=1;
ch.upd(now,1);
}
}else if(c=='c'){
int now;
cin>>now;
if(broke[now]){
broke[now]=0;
ch.upd(now,-1);
}else {
broke[now]=1;
ch.upd(now,1);
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
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 #2:
score: 0
Accepted
time: 0ms
memory: 5604kb
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: 290ms
memory: 36228kb
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 35339400 impossible 20157200 impossible impossible impossible impossib...
result:
wrong answer 464th lines differ - expected: '637000', found: 'impossible'