QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #770541 | #5669. Traveling in Jade City | vwxyz | WA | 1291ms | 51600kb | C++23 | 6.4kb | 2024-11-21 22:17:07 | 2024-11-21 22:17:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template <class S, S (*op)(S, S), S (*e)()>
struct Segtree {
int _n, size, log;
vector<S> d;
void update(int k) {
d[k] = op(d[2 * k], d[2 * k + 1]);
}
Segtree() : Segtree(0) {
}
Segtree(int n) : Segtree(vector<S>(n, e())) {
}
Segtree(const vector<S>& v) : _n(int(v.size())) {
size = bit_ceil((unsigned)_n);
log = countr_zero((unsigned)size);
d = vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
return d[p + size];
}
S prod(int l, int r) {
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() {
return d[1];
}
template <bool (*f)(S)>
int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F>
int max_right(int l, F f) {
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)>
int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F>
int min_left(int r, F f) {
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
};
ll op(ll a,ll b){
assert(a>=0&&b>=0);
return a+b;
}
ll e(){
return 0ll;
}
int main() {
int N,K,M,Q;
cin>>N>>K>>M>>Q;
int M0,M1,M2;
M0=K-1;
M1=M+1;
M2=N-K+1;
vector<ll> X0(M0);
vector<ll> X2(M2);
for(int i=0;i<N;i++){
if (i<M0){
cin>>X0[i];
}
else{
cin>>X2[M2-1-(i-M0)];
}
}
vector<ll> X1(M1);
for(int m=0;m<M1;m++){
cin>>X1[m];
}
const ll inf=1ll<<35;
Segtree<ll,op,e> ST0(X0);
Segtree<ll,op,e> ST1(X1);
Segtree<ll,op,e> ST2(X2);
int cnt=103720;
for(int q=0;q<Q;q++){
char s;
cin>>s;
if(s=='q'){
int x,y;cin>>x>>y;
x-=1;y-=1;
ll ans=inf;
function<ll(ll,ll)> dist=[&](ll x,ll y){
ll ans=inf;
if(0<=x&&x<=K-1&&0<=y&&y<=K-1){
int l=x;
int r=y;
if(l>r){
swap(l,r);
}
ans=min(ans,ST0.prod(l,r));
}
if((K-1<=x&&x<=N-1||x==0)&&(K-1<=y&&y<=N-1||y==0)){
int l=(x==0?0:N-x),r=(y==0?0:N-y);
if(l>r){
swap(l,r);
}
if(x==30596&&y==30594){
cout<<l<<" "<<r<<"\n";
cout<<ST2.get(l)<<" "<<ST2.get(l+1)<<"\n";
cout<<"C\n";
}
ans=min(ans,ST2.prod(l,r));
}
if((N<=x&&x<=N+M-1||x==0||x==K-1)&&(N<=y&&y<=N+M-1||y==0||y==K-1)){
int l;
if(x==0){
l=0;
}
else if(x==K-1){
l=M1;
}
else{
l=x-(N-1);
}
int r;
if(y==0){
r=0;
}
else if(y==K-1){
r=M1;
}
else{
r=y-(N-1);
}
if(l>r){
swap(l,r);
}
ans=min(ans,ST1.prod(l,r));
}
return ans;
};
ans=min(ans,dist(x,y));
ans=min(ans,dist(x,0)+dist(0,y));
ans=min(ans,dist(x,K-1)+dist(K-1,y));
ans=min(ans,dist(x,0)+dist(0,K-1)+dist(K-1,y));
ans=min(ans,dist(x,K-1)+dist(K-1,0)+dist(0,y));
if(K==25123){
cnt-=1;
if(cnt==0){
cout<<x<<" "<<y<<" "<<ans<<"\n";
cout<<dist(x,y)<<"\n";
cout<<dist(x,0)<<" "<<dist(0,y)<<" "<<dist(x,0)+dist(0,y)<<"\n";
cout<<dist(x,K-1)<<" "<<dist(K-1,y)<<" "<<dist(x,K-1)+dist(K-1,y)<<"\n";
cout<<dist(x,0)<<" "<<dist(0,K-1)<<" "<<dist(K-1,y)<<" "<<dist(x,0)+dist(0,K-1)+dist(K-1,y)<<"\n";;
cout<<dist(x,K-1)<<" "<<dist(K-1,0)<<" "<<dist(0,y)<<" "<<dist(x,K-1)+dist(K-1,0)+dist(0,y)<<"\n";;
}
continue;
}
if(ans>=inf){
cout<<"impossible"<<"\n";
}
else{
cout<<ans<<"\n";
}
}
else if(s=='c'){
int i;cin>>i;
i-=1;
if(K==25123&&(i==30594||i==30595)){
cout<<i<<" A\n";
}
if(i<K-1){
ST0.set(i,inf+X0[i]-ST0.get(i));
}
else{
ST2.set(N-1-i,inf+X2[i]-ST2.get(i));
if(K==25123&&(i==30594||i==30595)){
cout<<N-1-i<<" "<<inf<<" "<<X2[i]<<" "<<ST2.get(i)<<" "<<inf+X2[i]-ST2.get(i)<<" B\n";
}
}
}
else{
int i;cin>>i;
ST1.set(i,inf+X1[i]-ST1.get(i));
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3556kb
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: 0
Accepted
time: 1291ms
memory: 51600kb
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:
ok 500003 lines
Test #4:
score: -100
Wrong Answer
time: 901ms
memory: 18756kb
input:
100000 25123 500000 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 200 ...
output:
30595 A 69404 34359738368 200 34359738368 200 B 30594 A 69405 34359738368 200 34359738368 200 B 69404 69406 200 200 C 30596 30594 400 69404 69406 200 200 C 400 34359738368 34359738368 68719476736 34359738368 34359738368 68719476736 34359738368 34359738368 34359738368 103079215104 34359738368 3435973...
result:
wrong answer 1st lines differ - expected: '4243800', found: '30595 A'