QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #139194 | #5669. Traveling in Jade City | hano# | Compile Error | / | / | C++20 | 4.8kb | 2023-08-12 19:36:26 | 2023-08-12 19:36:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n,k,m,q;
long long c[N];
long long x[N];
long long pc[N];
long long px[N];
set<int> rc, rx;
int solve(int x,int y){
if(x > y){
swap(x,y);
}
int ans = 2e9;
// 1 -> 1 (<k)
if(1 <= x && x < k && 1 <= y && y < k){
// x -> y direct
if(*rc.lower_bound(x) >= y){
ans = min(ans, pc[y-1] - pc[x-1]);
}
// x -> y reverse
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through m
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) >= k && *rx.lower_bound(0) == N+N){
ans = min(ans, pc[x-1] + (pc[k-1] - pc[y-1]) + px[m+1]);
}
return ans;
}
// 1 -> 2 (<k -> <n)
if(1 <= x && x <= k && k <= y && y <= n){
// x -> y direct
//cout<<"HI"<<endl;
if(*rc.lower_bound(x) >= y){
//cout<<"x->y direct ";
ans = min(ans, pc[y-1] - pc[x-1]);
//cout<<ans<<endl;
}
// x -> y reverse
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through 1->k
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) == N+N && *rc.lower_bound(k) >= y){
ans = min(ans, pc[x-1] + px[m+1] + (pc[y-1] - pc[k-1]));
}
// x -> y through k->1
if(*rc.lower_bound(x) >= k && *rx.lower_bound(0) == N+N && *rc.lower_bound(y) == N+N){
ans = min(ans, (pc[k-1] - pc[x-1]) + px[m+1] + (pc[n] - pc[y-1]));
}
return ans;
}
// 1 -> 3 (<k -> >n) (exluding 1 and k)
if(1 <= x && x <= k && (n < y)){
// x -> k -> y
if(*rc.lower_bound(x) >= k && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[k-1]-pc[x-1]) + (px[m+1]-px[y-n+1-1]));
}
// x -> 1 -> y
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) >= y-n){
ans = min(ans, pc[x-1] + px[y-n+1-1]);
}
// x -> k -> 1 -> y
if(*rc.lower_bound(x) == N+N && *rx.lower_bound(0) >= y-n){
ans = min(ans, (pc[n] - pc[x-1]) + px[y-n+1-1]);
}
// x -> 1 -> k -> y
if(*rc.lower_bound(1) >= x && *rc.lower_bound(k) == N+N && *rx.lower_bound(y-n) == N+N){
ans = min(ans, pc[x-1] + (pc[n]-pc[k-1]) + (px[m+1]-px[y-n+1-1]));
}
return ans;
}
// 2 -> 2
if(k <= x && x <= n && k <= y && y <= n){
// x -> y direct
if(*rc.lower_bound(x) >= y){
ans = min(ans, pc[y-1] - pc[x-1]);
}
// x -> y reverse
if(*rc.lower_bound(0) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through m
if(*rx.lower_bound(0) == N+N && *rc.lower_bound(k) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, px[m+1] + (pc[n]-pc[y-1]) + (pc[x-1] - pc[k-1]));
}
return ans;
}
// 2 -> 3
if(k <= x && x <= n && (n < y)){
// x -> 1 -> y
if(*rc.lower_bound(y) == N+N && *rx.lower_bound(0) >= y-n){
ans = min(ans, (pc[n]-pc[x-1]) + px[y-n+1-1]);
}
// x -> k -> y
if(*rc.lower_bound(k) >= x && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[x-1] - pc[k-1]) + (px[m+1] - px[y-n+1-1]));
}
// x -> 1 -> k -> y
if(*rc.lower_bound(x) == N+N && *rc.lower_bound(1) >= k && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[n]-pc[x-1]) + pc[k-1] + (px[m+1]-px[y-n+1-1]));
}
// x -> k -> 1 -> y
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) >= y-n){
ans = min(ans, pc[x-1] + px[y-n+1-1]);
}
return ans;
}
// 3 -> 3
if((n < y) && (n < x)){
// x -> y direct
if(*rx.lower_bound(x-n) >= y-n){
ans = min(ans, px[y-n+1-1] - px[x-n+1-1]);
}
// x -> y reverse < k
if(*rx.lower_bound(0) >= x-n && *rx.lower_bound(y-n) == N+N && *rc.lower_bound(1) >= k){
ans = min(ans, px[x-n+1-1] + (px[m+1] - px[y-n+1-1]) + pc[k-1]);
}
// x -> y reverse > k
if(*rx.lower_bound(0) >= x-n && *rx.lower_bound(y-n) == N+N && *rc.lower_bound(k) == N+N){
ans = min(ans, px[x-n+1-1] + (px[m+1] - px[y-n+1-1]) + (pc[n] - pc[k-1]));
}
return ans;
}
//assert(1==2);
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k>>m>>q;
rc.insert(N+N);
rx.insert(N+N);
for(int i=1;i<=n;i++){
cin>>c[i];
pc[i] = pc[i-1] + c[i];
}
for(int i=1;i<=m+1;i++){
cin>>x[i];
px[i] = px[i-1] + x[i];
}
for(int i=0;i<q;i++){
char c;
cin>>c;
if(c == 'q'){
int x,y;
cin>>x>>y;
//cout<<solve(x,y)'\n';
int ans = solve(x,y);
if(ans >= 2e9){
cout<<"impossible\n";
}else{
cout<<ans<<'\n';
}
}
if(c == 'c'){
int x;
cin>>x;
if(rc.count(x))rc.erase(x);
else rc.insert(x);
}
if(c == 'x'){
int x;
cin>>x;
if(rx.count(x))rx.erase(x);
else rx.insert(x);
}
}
return 0;
}
/*
4 3 1 9
2 3 8 4
1 1
q 1 4
c 4
q 1 4
c 3
q 1 4
c 3
q 1 4
x 0
q 1 4
*/
/*
// same sector
if(1 <= x && x <= k && 1 <= y && y <= k){
}
if(k <= x && x <= n && k <= y && y <= n){
}
i(
// diff sector
*/
Details
answer.code: In function ‘int solve(int, int)’:
answer.code:25:34: error: no matching function for call to ‘min(int&, long long int)’
25 | ans = min(ans, pc[y-1] - pc[x-1]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
answer.code:25:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
25 | ans = min(ans, pc[y-1] - pc[x-1]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
answer.code:25:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
25 | ans = min(ans, pc[y-1] - pc[x-1]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)’
3449 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: template argument deduction/substitution failed:
answer.code:25:34: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
25 | ans = min(ans, pc[y-1] - pc[x-1]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)’
3455 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: template argument deduction/substitution failed:
answer.code:25:34: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
25 | ans = min(ans, pc[y-1] - pc[x-1]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:29:34: error: no matching function for call to ‘min(int&, long long int)’
29 | ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
answer.code:29:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
29 | ans = min(ans, pc[n] - (pc[y-1...