QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102776#5669. Traveling in Jade CityJolerWA 477ms81184kbC++206.8kb2023-05-03 17:38:222023-05-03 17:38:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 17:38:25]
  • 评测
  • 测评结果:WA
  • 用时:477ms
  • 内存:81184kb
  • [2023-05-03 17:38:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef LOCAL
template<class t,class u>ostream& operator<<(ostream& os,const pair<t,u>& p){return os<<"("<<p.first<<","<<p.second<<")";}
#endif
template<class t>ostream& operator<<(ostream& os,const vector<t>& v){if(v.size())os<<v[0];for(int i=1; i<v.size(); i++)os<<' '<<v[i]; return os;}
const int inf = 0x3f3f3f3f;
const ll INF = inf;
int n, m, t, k, a, b, c, d, cnt, mark, an, oT_To, x, y, z, q;
ll ans;

int check(int x) {
    int res = 0;
    if (x == 1 || x == k) res |= 7;
    if (x < k) res |= 1;
    if (x > k && x <= n) res |= 2;
    if (x > n) res |= 3;
}

template<typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n = 0) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }

    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }

    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};
struct Solver {
	void solve() {
        cin >> n >> k >> m >> q;
        vector <ll> vc (n+1), vx(m+1);
        vector vf(3, Fenwick<ll>(n+m+2) );
        auto VC(vc), VX(vx);
        for (int i = 1; i < k; ++i) {
            cin >> VC[i];
            vf[0].add(i+1, VC[i]);
        }
        for (int i = k; i <= n; ++i) {
            cin >> VC[i];
            vf[1].add(i+1, VC[i]);
        }

        for (int i = 0; i <= m; ++i) {
            cin >> VX[i];
            vf[2].add(i+2, VX[i]);
        }

        auto get1 = [&](int x){
            ll res = INF;
            if (x > n) {
                x -= n;
                return vf[2].rangeSum(1, x+1);
            } else {
                if (x >= k) {
                    res = min(res, vf[1].rangeSum(x+1, n+2));
                }
                if (x <= k) {
                    res = min(res, vf[0].rangeSum(1, x+1));
                }
            }
            return res;
        };

        auto getk = [&](int x) {
            ll res = INF;
            if (x > n) {
                x -= n;
                return vf[2].rangeSum(x+1, m+2);
            } else {
                if (x >= k) {
                    res = min(res, vf[1].rangeSum(k+1, x+1));
                } else {
                    res = min(res, vf[0].rangeSum(x+1, k+1));
                }
            }
            return res;
        };
//        cout << "vf[0].rangeSum(2, 4): " << vf[0].rangeSum(4, 5) << '\n';
        char ch;
        while (q--) {
            cin >> ch;
            if (ch == 'x') {
                cin >> a;
                if (vx[a]) {
                    vf[2].add(a+2, -INF);
                } else {
                    vf[2].add(a+2, INF);
                }
                vx[a] = !vx[a];
            } else if (ch == 'c') {
                cin >> a;
                if (vc[a]) {
                    if (a < k) {
                        vf[0].add(a+1, -INF);
                    } else {
                        vf[1].add(a+1, -INF);
                    }
                } else {
                    if (a < k) {
                        vf[0].add(a+1, INF);
                    } else {
                        vf[1].add(a+1, INF);
                    }
                }
                vc[a] = !vc[a];
            } else if (ch == 'q') {
                cin >> a >> b;
                if (a > b) swap(a, b);
                ll a1 = get1(a), ak = getk(a);
                ll b1 = get1(b), bk = getk(b);
                ll k1 = vf[2].sum(m+3);
                ans = min({INF, a1+b1, ak+bk, a1+k1+bk, ak+k1+b1});
                if (a > n && b > n) {
                    ans = min(ans, vf[2].rangeSum(a+2, b+2));
                } else {
                    if (a >= k && b >= k) {
                        ans = min(ans, vf[1].rangeSum(a+1, b+1));
                    }
                    if (a <= k && b <= k) {
                        ans = min(ans, vf[0].rangeSum(a+1, b+1));
                    }
                }
                if (ans >= INF) {
                    cout << "impossible\n";
                } else cout << ans << '\n';
            }
        }

//
//        v1[0][1] = v1[1][1] = v1[2][1] = 0;
//        vk[0][k] = vk[1][k] = vk[2][k] = 0;
//        // 0 -> 1-k
//        for (int i = 2; i <= k; ++i) {
//            v1[0][i] = v1[0][i-1] + vc[i-1];
//        }
//        for (int i = k-1; i >= 1; --i) {
//            vk[0][i] = vk[0][i+1] + vc[i];
//        }
//
//        // 1 -> k-n
//        for (int i = k+1; i <= n; ++i) {
//            vk[1][i] = vk[1][i-1] + vc[i-1];
//        }
//        v1[1][n+1] = 0;
//        for (int i = n; i >= k; --i) {
//            v1[1][i] = v1[1][i+1] + vc[i];
//        }
//        vk[1][1] = v1[1][k];
//        v1[1][n+1] = INF;
//
//
//
//        // 2 -> 1-n+1-n+m-k
//        v1[2][n+1] = vx[0];
//        for (int i = n+2; i <= n+m; ++i) {
//            v1[2][i] = v1[2][i-1] + vx[i-n-1];
//        }
//        vk[2][1] = v1[2][k] = v1[2][n+m] + vx[m];
//        vk[2][n+m+1] = 0;
//        for (int i = n+m; i >= n+1; --i) {
//            vk[2][i] = vk[2][i+1] + vx[i - n];
//        }
//        vk[2][n+m+1] = INF;
//
//
//
//        while (vp.size()) {
//            auto [x, y] = vp.back(); vp.pop_back();
//            if (y > 0) {
//                ans = INF;
//                int fx = check(x), fy = check(y);
//                ll xto1 = min({v1[0][x], v1[1][x], v1[2][x]});
//                ll xtok = min({vk[0][x], vk[1][x], vk[2][x]});
//                ll yto1 = min({v1[0][y], v1[1][y], v1[2][y]});
//                ll ytok = min({vk[0][y], vk[1][y], vk[2][y]});
//                ans = min({ans, xto1 + yto1, xtok + ytok, xto1 + v1[2][k] + ytok, xtok + v1[2][k] + yto1});
//                for (int i : {0, 1, 2}) {
//                    int j = i<<1;
//                    if ((fx&j) && (fy&j)) {
//                        ans = min(ans, abs(v1[i][x] - v1[])
//                    }
//                }
//
//            }
//            else {
//                y = -y;
//                if (x == 0) {
//                    vx[y] = VX[y];
//                    // do it
//                    assert(0);
//                } else {
//                    vc[y] = VX[y];
//                    // do it
//                    assert(0);
//
//                }
//            }
//        }


	}
};

int main () {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    cout << "INF: " << INF << '\n';
    oT_To = 1;
//    cin >> oT_To;
    while (oT_To--) {
    	Solver solver;
        solver.solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

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: 1ms
memory: 3380kb

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: 477ms
memory: 81184kb

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:

377406200
122264600
181690400
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
29295000
impossible
22163000
impossible
impossible
impossible
0
impossible
0
impossible
0
impossible
0
impossible
impossible
impossible
impossible
impossible
0
impossible
...

result:

wrong answer 1st lines differ - expected: '177406400', found: '377406200'