QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102772#5669. Traveling in Jade CityJoler#WA 457ms81116kbC++236.8kb2023-05-03 17:37:042023-05-03 17:37:20

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:37:20]
  • 评测
  • 测评结果:WA
  • 用时:457ms
  • 内存:81116kb
  • [2023-05-03 17:37:04]
  • 提交

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, abs(a1-b1));
                } 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: 3452kb

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: 3372kb

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: 457ms
memory: 81116kb

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
11422200
impossible
62579800
impossible
164661200
impossible
20157200
impossible
impossible
impossible
imposs...

result:

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