QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184583 | #5669. Traveling in Jade City | Anwar# | WA | 267ms | 20616kb | C++23 | 2.9kb | 2023-09-20 21:34:31 | 2023-09-20 21:34:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 5 , MOD = 1e9 + 7 ;
vector<int> BIT[2] ;
void add(vector<int> & BIT , int i , int val)
{
i++;
while(i <= (int)BIT.size() )
{
BIT[i-1] += val;
i += i & -i ;
}
}
int get(vector<int> & BIT , int i)
{
i++;
int ans= 0;
while(i > 0)
{
ans += BIT[i-1];
i -= i & - i ;
}
return ans ;
}
int n , k ,m , q ;
ll sum[2] ;
void pri(ll x){
if(x >= 1e9) cout << "impossible\n" ;
else cout << x << "\n" ;
}
ll getCir(int u , int v)
{
if(u > v)swap(u , v);
ll dis = get(BIT[0] , v-1) - get(BIT[0] , u-1) ;
return min( dis , sum[0] - dis ) ;
}
ll getLin(int u , int v)
{
if(u > v) swap(u , v ) ;
ll dis = get(BIT[1] , v-1) - get(BIT[1] , u-1) ;
return min( dis , sum[1] - dis + getCir(1 , k) ) ;
}
bool val[N];
int main()
{
cin.tie(0);cin.sync_with_stdio(0);
cout.tie(0);cout.sync_with_stdio(0);
cin >> n >> k >> m >> q;
BIT[0].resize(n+5) ;
int a[n+1] , b[m+2] ;
for(int i = 1 ; i <= n; i++)
{
int x ;
cin >> x;
sum[0] += x;
add(BIT[0] , i , x) ;
a[i] = x;
}
BIT[1].resize(m+6) ;
for (int i = 1 ; i <= m + 1; ++i) {
int x ;
cin >> x;
add(BIT[1] , i , x) ;
sum[1] += x;
b[i] = x;
}
for(int i = 1 ; i <= n+m + 3;i++) val[i] = 1 ;
while (q--)
{
char c;
cin >> c;
if(c == 'q')
{
int u , v ;
cin >> u >> v;
if(v < u) swap(u , v) ;
if(v <= n) pri ( min( { getCir(u , v) , getCir(u ,1 ) + sum[1] + getCir(k , v) , getCir(u ,k ) + sum[1] + getCir(1 , v) } ) );
else if(u > n) pri (getLin(u , v) ) ;
else pri( min( getCir(1 , u) + getLin(1 , v) , getCir( u , k ) + getLin(v , k) ) ) ;
}
else if(c == 'c')
{
int x;
cin >> x;
if(val[x])
{
add( BIT[0] , x , -a[x] + 1e9 ) ;
sum[0] += -a[x] + 1e9 ;
}
else
{
add( BIT[0] , x , -1e9 + a[x] ) ;
sum[0] += -1e9 + a[x] ;
}
val[x] ^= 1;
}
else
{
int x;
cin >> x;
x++ ;
if(val[x+n])
{
add( BIT[1] , x , -b[x] + 1e9 ) ;
sum[1] += -b[x] + 1e9 ;
}
else
{
add( BIT[1] , x , -1e9 + b[x] ) ;
sum[1] += -1e9 + b[x] ;
}
val[x+n] ^= 1;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3448kb
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: 3436kb
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: 267ms
memory: 20616kb
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 -4024735192 -1817118592 impossible 66061904 impossible impossible -1438343296 -441306896 -668945992 -537626584 impossible 12002400 -933648288 -3572398168 525852128 -1484583896 146502120 -456200 -2549948272 -75980680 -1324104280 616400 -1825829288 -1372148376 -1527721280 431279712 -65866147...
result:
wrong answer 2nd lines differ - expected: '122264600', found: '-4024735192'