Submission #674046

#	Time	Username	Problem	Language	Result	Execution time	Memory
674046		doowey	Fish 2 (JOI22_fish2)	C++14	100 / 100	2224 ms	46620 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;

ll S[N];

struct segm{
    ll sum;
    int id;
    int cnt;
};

bool compL(segm p1, segm p2){
    return p1.id < p2.id;
}

bool compR(segm p1, segm p2){
    return p1.id > p2.id;
}

struct Node{
    vector<segm> pref;
    vector<segm> suff;
    int lef;
    int rig;
};

Node T[N * 4 + 512];

Node unite(Node A, Node B){
    Node res;
    res.pref = A.pref;
    res.suff = B.suff;
    res.lef = A.lef;
    res.rig = B.rig;
    res.pref.pop_back();
    res.suff.pop_back();
    int ii, jj;
    ll sum;
    int idx;

    for(int i = 0 ; i < A.suff.size(); i ++ ){
        ii = i;
        jj = 0;
        sum = 0;
        while(1){
            sum = A.suff[ii].sum;
            if(jj) sum += B.pref[jj - 1].sum;
            if(ii + 1 < A.suff.size()){
                if(sum >= S[A.suff[ii].id - 1]){
                    ii ++ ;
                    continue;
                }
            }
            if(jj < B.pref.size()){
                if(jj == 0) idx = A.rig + 1;
                else idx = B.pref[jj - 1].id + 1;
                if(sum >= S[idx]){
                    jj ++ ;
                    continue;
                }
            }
            break;
        }
        if(ii + 1 == A.suff.size()){
            if(jj == 0) idx = A.rig;
            else idx = B.pref[jj - 1].id;
            res.pref.push_back({sum, idx, A.suff[i].cnt});
        }
        if(jj == B.pref.size()){
            res.suff.push_back({sum, A.suff[ii].id, A.suff[i].cnt});
        }
    }
    for(int i = 0 ; i < B.pref.size(); i ++ ){
        ii = 0;
        jj = i;
        sum = 0;
        while(1){
            sum = B.pref[jj].sum;
            if(ii) sum += A.suff[ii - 1].sum;
            if(jj + 1 < B.pref.size()){
                if(sum >= S[B.pref[jj].id + 1]){
                    jj ++ ;
                    continue;
                }
            }
            if(ii < A.suff.size()){
                if(ii == 0) idx = B.lef - 1;
                else idx = A.suff[ii - 1].id - 1;
                if(sum >= S[idx]){
                    ii ++ ;
                    continue;
                }
            }
            break;
        }
        if(ii == A.suff.size()){
            res.pref.push_back({sum, B.pref[jj].id, B.pref[i].cnt});
        }
        if(jj + 1 == B.pref.size()) {
            if(ii == 0) idx = B.lef;
            else idx = A.suff[ii - 1].id;
            res.suff.push_back({sum, idx, B.pref[i].cnt});
        }
    }
    sort(res.pref.begin(), res.pref.end(), compL);
    sort(res.suff.begin(), res.suff.end(), compR);
    vector<segm> lap;
    vector<segm> rap;
    for(auto it : res.pref){
        if(lap.empty() || lap.back().id != it.id){
            lap.push_back(it);
        }
        else{
            lap.back().cnt += it.cnt;
        }
    }
    for(auto it : res.suff){
        if(rap.empty() || rap.back().id != it.id){
            rap.push_back(it);
        }
        else{
            rap.back().cnt += it.cnt;
        }
    }
    res.pref = lap;
    res.suff = rap;
    return res;
}

Node outp;
bool vv;

void get(int node, int cl, int cr, int tl, int tr){
    if(node == 1) vv = false;
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(!vv){
            outp=T[node];
            vv=true;
        }
        else{
            outp=unite(outp,T[node]);
        }
        return;
    }
    int mid = (cl + cr) / 2;
    get(node * 2, cl, mid, tl, tr);
    get(node * 2 + 1, mid + 1, cr, tl, tr);
}

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].pref = {{S[cl], cl, 1}};
        T[node].suff = {{S[cl], cl, 1}};
        T[node].lef = cl;
        T[node].rig = cr;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

void upd(int node, int cl, int cr, int target){
    if(cl == cr){
        T[node].pref = {{S[cl], cl, 1}};
        T[node].suff = {{S[cl], cl, 1}};
        T[node].lef = cl;
        T[node].rig = cr;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= target) upd(node * 2, cl, mid, target);
    else upd(node * 2 + 1, mid + 1, cr, target);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> S[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    int typ;
    int li, ri;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> typ;
        if(typ == 1){
            cin >> li >> ri;
            S[li]=ri;
            upd(1, 1, n, li);
        }
        else{
            cin >> li >> ri;
            get(1, 1, n, li, ri);
            cout << outp.suff.back().cnt << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'Node unite(Node, Node)':
fish2.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0 ; i < A.suff.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~~~~
fish2.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if(ii + 1 < A.suff.size()){
      |                ~~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(jj < B.pref.size()){
      |                ~~~^~~~~~~~~~~~~~~
fish2.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if(ii + 1 == A.suff.size()){
      |            ~~~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if(jj == B.pref.size()){
      |            ~~~^~~~~~~~~~~~~~~~
fish2.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0 ; i < B.pref.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~~~~
fish2.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             if(jj + 1 < B.pref.size()){
      |                ~~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if(ii < A.suff.size()){
      |                ~~~^~~~~~~~~~~~~~~
fish2.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         if(ii == A.suff.size()){
      |            ~~~^~~~~~~~~~~~~~~~
fish2.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(jj + 1 == B.pref.size()) {
      |            ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17