QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#86818	#5000. Balanced Seesaw Array	camilo_alvarez09	WA	341ms	22248kb	C++17	7.3kb	2023-03-11 08:42:45	2023-03-11 08:42:47

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-11 08:42:47]
评测

测评结果：WA
用时：341ms
内存：22248kb

查看

[2023-03-11 08:42:45]
提交

answer

#include <bits/stdc++.h>

#define fi first
#define se second
#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define for1(i, n) for (int i = 1; i <= (int)n; ++i)
#define fore(i, l, r) for (int i = (int)l; i <= (int)r; ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define fored(i, l, r) for (int i = (int)r; i >= (int)l; --i)
#define pb push_back
#define el '\n'
#define DBG(x) cerr << #x << " = " << x << endl
#define RAYA cerr << "=============================" << endl
#define d(x) cerr << #x << " " << x << el
#define ri(n) scanf("%d", &n)
#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define is_odd(n) ((int) n & 1)

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int, int> ii;
typedef pair<char, int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll, ll> pll;
typedef vector<char> vc;
typedef vector<int> vi;

const int inf = 2147483647;
const int nax = 1e5 + 200;
const ld pi = acos(-1);
const ld eps = 2250738585072014e-308;


struct  mynum{
    ll ai, aii;
    bool reset;
    mynum() {
        ai = 0;
        aii = 0;
        reset = false;
    }
};

#define neutro mynum()

ll calc_aii(ll val, ll l, ll r){
    ll num, sum1, sum2;
    sum1 = (l*(l-1))/2;
    sum2 = (r*(r+1))/2;
    num = val*(sum2-sum1);
    return num;
}

ll calc_ai(ll val, ll l, ll r){
    ll num;
    num = val*(r-l+1);
    return num;
}

struct stree{
    int n;   vector<mynum> t, lazy;
    stree(int m){
        n = m;    t.resize(n<<2);
        lazy.resize(n<<2);
    }
    stree(vector<int> &a){
        n = sz(a); t.resize(n<<2);   lazy.resize(n<<2);
        build(1,0, n-1, a);
    }

    inline ll oper(ll a, ll b){ return a+b; }

    void build(int v, int tl, int tr, vector<int> &a){
        if(tl==tr){
            t[v].ai = a[tl]; 
            t[v].aii = a[tl]*tl;
            return ;
        }
        int tm = tl + (tr-tl)/ 2;
        build(v*2, tl, tm, a);
        build(v*2+1, tm+1, tr, a);
        t[v].ai = oper(t[v*2].ai, t[v*2+1].ai);
        t[v].aii = oper(t[v*2].aii, t[v*2+1].aii);

    }

    

    void push(int v, int tm, int tl, int tr) {
        ll vali = lazy[v].ai;
        ll valii = lazy[v].aii;

        ll valiLeft = calc_ai(vali, tl, tm);
        ll valiiLeft = calc_aii(valii, tl, tm);

        ll valiRight = calc_ai(vali, tm+1, tr);
        ll valiiRight = calc_aii(valii, tm+1, tr);

        if(lazy[v].reset){
            t[v*2].ai = 0; lazy[v*2].ai = 0; //Left
            t[v*2+1].ai = 0; lazy[v*2+1].ai = 0; // Right

            t[v*2].aii = 0; lazy[v*2].aii = 0; //Left
            t[v*2+1].aii = 0; lazy[v*2+1].aii = 0; // Right

            lazy[v].reset = false;
            lazy[v*2].reset = true;
            lazy[v*2+1].reset = true;
        }

        t[v*2].ai += valiLeft; lazy[v*2].ai += lazy[v].ai; //Left
        t[v*2+1].ai += valiRight; lazy[v*2+1].ai += lazy[v].ai; // Right
        lazy[v].ai = 0;

        t[v*2].aii += valiiLeft; lazy[v*2].aii += lazy[v].aii; //Left
        t[v*2+1].aii += valiiRight; lazy[v*2+1].aii += lazy[v].aii; // Right
        lazy[v].aii = 0;

    }

    void upd1(int v, int tl, int tr, int l, int r, int val) {
        
        if(tl>r || tr<l) return ;

        if (l <= tl && tr <= r) {
            ll vali = calc_ai(val, tl, tr);
            ll valii = calc_aii(val, tl, tr);

            t[v].ai += vali;
            lazy[v].ai += val;
            
            t[v].aii += valii;
            lazy[v].aii += val;

            return ;
        }
        
        int tm = tl + (tr-tl)/ 2;
        push(v, tm, tl, tr);

        upd1(v*2, tl, tm, l, r, val);
        upd1(v*2+1, tm+1, tr, l, r, val);
        t[v].ai = oper(t[v*2].ai, t[v*2+1].ai);
        t[v].aii = oper(t[v*2].aii, t[v*2+1].aii);
    }

    void upd2(int v, int tl, int tr, int l, int r, int val) {
        
        if(tl>r || tr<l) return ;

        if (l <= tl && tr <= r) {
            ll vali = calc_ai(val, tl, tr);
            ll valii = calc_aii(val, tl, tr);

            t[v].ai = 0;
            lazy[v].ai = 0;
            
            t[v].aii = 0;
            lazy[v].aii = 0;

            t[v].ai += vali;
            lazy[v].ai += val;
            
            t[v].aii += valii;
            lazy[v].aii += val;

            lazy[v].reset = true;
            return ;
        }
        
        int tm = tl + (tr-tl)/ 2;
        push(v, tm, tl, tr);

        upd2(v*2, tl, tm, l, r, val);
        upd2(v*2+1, tm+1, tr, l, r, val);
        t[v].ai = oper(t[v*2].ai, t[v*2+1].ai);
        t[v].aii = oper(t[v*2].aii, t[v*2+1].aii);
    }

    mynum query(int v, int tl, int tr, int l, int r) {
        if(tl>r || tr<l) return neutro;
        if (l <= tl && tr <= r) return t[v];
        int tm = tl + (tr-tl)/ 2;
        push(v, tm, tl, tr);

        mynum temp1 = query(v*2, tl, tm, l, r);
        mynum temp2 = query(v*2+1, tm+1, tr, l, r);

        mynum temp3;
        temp3.ai = oper(temp1.ai, temp2.ai);
        temp3.aii = oper(temp1.aii, temp2.aii);
        return temp3;
    }

    void upd1(int l, int r, int val){ upd1(1,0,n-1,l, r,val); }
    void upd2(int l, int r, int val){ upd2(1,0,n-1,l, r,val); }
    mynum query(int l, int r){ return query(1,0,n-1,l,r); }
};




// g++ -std=c++11 -g -O2 -Wconversion -Wshadow -Wall -Wextra -D_GLIBCXX_DEBUG B.cpp -o B
int main()
{
// freopen('i.txt', 'r', stdin);
// freopen('o.txt', 'w', stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << setprecision(20) << fixed;
    int n, q; cin >> n >> q;
    vector<int> arr(n);
    forn(i, n) cin >> arr[i];
    stree mys = stree(arr);

    while(q--){
        int type, l, r, x; cin >> type;

        if(type == 1){
            cin >> l >> r >> x;
            l--;
            r--;
            mys.upd1(l, r, x);

            // forn(i, n){
            //     mynum temp = mys.query(i, i);
            //     cout << temp.ai << " " << temp.aii << el;
            // }
            // cout << " ++++++++++++++++++++++++++++++" << el;
        }else if (type == 2){
            cin >> l >> r >> x;
            l--;
            r--;
            mys.upd2(l, r, x);
            // forn(i, n){
            //     mynum temp = mys.query(i, i);
            //     cout << temp.ai << " " << temp.aii << el;
            // }
            // cout << " ++++++++++++++++++++++++++++++" << el;
        }else{
            cin >> l >> r;
            l--;
            r--;
            // forn(i, n){
            //     mynum temp = mys.query(i, i);
            //     cout << temp.ai << " " << temp.aii << el;
            // }
            // cout << " ++++++++++++++++++++++++++++++" << el;
            mynum tempNum = mys.query(l, r);
            ll valaii =  tempNum.aii;
            ll valai = tempNum.ai;
            if(valai == 0){
                cout << "No" << el;
                continue;
            }
            ll k = valaii/valai;
            // DBG(l);
            // DBG(r);
            // DBG(valaii);
            // DBG(valai);
            // DBG(k);
            // RAYA;
            if(valaii%valai == 0  && l <= k && k <= r) cout << "Yes" <<el;
            else cout << "No" << el;
        }


    }    
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3392kb

input:

output:

Yes
No
Yes
Yes

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 341ms

memory: 22248kb

input:

100000 451163
-18 609 -793 393 375 313 -55 -892 -446 928 -207 -390 729 -383 27 318 -400 31 -661 202 -978 212 238 -368 351 -613 -23 400 809 1000 -431 -174 -103 886 73 -150 25 820 -689 972 777 794 -36 -231 -966 632 -418 -288 -476 725 -713 -379 896 -19 -883 338 -797 937 -557 -809 -241 -539 704 44 576 -...

output:

No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
No...

result:

wrong answer 8252nd lines differ - expected: 'Yes', found: 'No'