QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184596 | #5669. Traveling in Jade City | Anwar# | WA | 311ms | 28564kb | C++23 | 2.9kb | 2023-09-20 21:52:02 | 2023-09-20 21:52:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 5 , MOD = 1e9 + 7 ;
vector<ll> BIT[2] ;
void add(vector<ll> & BIT , int i , int val)
{
i++;
while(i <= (ll)BIT.size() )
{
BIT[i-1] += val;
i += i & -i ;
}
}
ll get(vector<ll> & BIT , int i)
{
i++;
ll 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 - n , v - n) ) ;
else pri( min( getCir(1 , u) + getLin(1 , v-n) , getCir( u , k ) + getLin(v - n , m+1) ) ) ;
}
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: 0ms
memory: 3672kb
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: 3696kb
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: 311ms
memory: 28564kb
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 29295000 impossible 22163000 impossible impossible impossible 11422200 impossible 62579800 impossible 35339400 impossible 20157200 impossible impossible impossible impossib...
result:
wrong answer 13th lines differ - expected: '29295200', found: '29295000'