Submission #568745

#	Time	Username	Problem	Language	Result	Execution time	Memory
568745		tqbfjotld	Fish 2 (JOI22_fish2)	C++14	100 / 100	3941 ms	117532 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 999999999999999999LL;

struct dat{
    vector<int> lblockvals;
    vector<int> lblockpos;
    vector<int> lblocknum;
    vector<int> lblockpsum;
    vector<int> rblockvals;
    vector<int> rblockpos;
    vector<int> rblocknum;
    vector<int> rblockpsum;
    int numfin;
    int totsz;
    int len;
    dat(){
        numfin = 0;
        totsz = 0;
        len = 0;
    }
    dat(int num){
        numfin = 1;
        totsz = num;
        len = 1;
        lblockpos.push_back(0);
        lblocknum.push_back(0);
        lblockvals.push_back(num);
        lblockpsum.push_back(num);
        rblockpos.push_back(0);
        rblocknum.push_back(0);
        rblockvals.push_back(num);
        rblockpsum.push_back(num);
    }
};

dat mer(dat a, dat b){
    //printf("mer %d and %d\n",a.numfin,b.numfin);
    dat ans = dat();
    ans.totsz = a.totsz+b.totsz;
    ans.len = a.len+b.len;
    for (int x = 0; x<a.lblocknum.size(); x++){
        ans.lblocknum.push_back(a.lblocknum[x]);
        ans.lblockpos.push_back(a.lblockpos[x]);
        ans.lblockvals.push_back(a.lblockvals[x]);
        ans.lblockpsum.push_back(a.lblockpsum[x]);
        //printf("lblock %d %d %d %d\n",a.lblocknum[x],a.lblockpos[x],a.lblockvals[x],a.lblockpsum[x]);
    }
    for (int x = 0; x<b.rblocknum.size(); x++){
        ans.rblocknum.push_back(b.rblocknum[x]);
        ans.rblockpos.push_back(b.rblockpos[x]);
        ans.rblockvals.push_back(b.rblockvals[x]);
        ans.rblockpsum.push_back(b.rblockpsum[x]);
        //printf("rblock %d %d %d %d\n",b.rblocknum[x],b.rblockpos[x],b.rblockvals[x],b.rblockpsum[x]);
    }
    //printf("hi\n");
    int t1 = a.totsz;
    int li,ri;
    bool canfin = true;
    for (int x = 0; x<b.lblocknum.size(); x++){
        if (b.lblockvals[x]<=t1){
            t1 += b.lblockpsum[x];
            if (t1>INF) t1 = INF;
        }
        else{
            li = ans.lblocknum.size();
            canfin = false;
            //assert(!ans.lblockpsum.empty());
            ans.lblockpsum.back() += t1-a.totsz;
            ans.lblockpos.push_back(b.lblockpos[x]+a.len);
            ans.lblocknum.push_back(a.numfin);
            ans.lblockvals.push_back(b.lblockvals[x]);
            ans.lblockpsum.push_back(b.totsz-(t1-a.totsz));
            break;
        }
    }
    if (canfin){
        ans.lblockpsum.back() += b.totsz;
        ans.numfin += a.numfin;
    }
    t1 = b.totsz;
    canfin = true;
    for (int x = 0; x<a.rblocknum.size(); x++){
        if (a.rblockvals[x]<=t1){
            t1 += a.rblockpsum[x];
            if (t1>INF) t1 = INF;
        }
        else{
            ri = ans.rblocknum.size();
            canfin = false;
            //assert(!ans.rblockpsum.empty());
            ans.rblockpsum.back() += t1-b.totsz;
            ans.rblockpos.push_back(a.rblockpos[x]+b.len);
            ans.rblocknum.push_back(b.numfin);
            ans.rblockvals.push_back(a.rblockvals[x]);
            ans.rblockpsum.push_back(a.totsz-(t1-b.totsz));
            break;
        }
    }
    if (canfin){
        ans.rblockpsum.back() += a.totsz;
        ans.numfin += b.numfin;
    }
    //printf("hi\n");
    t1 = 0;
    int t2 = 0;
    int maxv = 0;
    long long sum1 = 0;
    for (int x = 0; x<a.rblocknum.size(); x++){
        sum1+= a.rblockpsum[x];
    }
    for (int x = 1; x<a.rblocknum.size(); x++){
        //printf("arblock %d %d %d %d\n",a.rblocknum[x],a.rblockpos[x],a.rblockvals[x],a.rblockpsum[x]);
        t1 += a.rblocknum[x];
        t2 += a.rblockpsum[x-1];
        sum1 -= a.rblockpsum[x-1];
        t2 = min(t2,INF);
        bool added = false;
        while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
            t2 += b.lblockpsum[maxv];
            t2 = min(t2,INF);
            maxv++;
            added = true;
        }
        if (a.rblockvals[x]>t2){
            if (maxv==b.lblocknum.size()){
                if (ans.rblockpos.back()==b.len+a.rblockpos[x]){
                    ans.rblocknum.back()+=t1;
                }
                else{
                    ans.rblockpsum.back() -= sum1;
                    ans.rblockpos.push_back(b.len+a.rblockpos[x]);
                    ans.rblocknum.push_back(t1);
                    ans.rblockvals.push_back(a.rblockvals[x]);
                    ans.rblockpsum.push_back(sum1);
                }
            }
            t1 = 0;
        }
    }
    t2 += a.rblockpsum.back();
    while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
        t2 += b.lblockpsum[maxv];
        t2 = min(t2,INF);
        maxv++;
    }
    //printf("maxv = %d\n",maxv);
    if (maxv==b.lblocknum.size()){
        ans.numfin += t1;
    }
    else{
        ans.lblocknum[li] += t1;
    }
    t1 = 0;
    t2 = 0;
    maxv = 0;
    int sum2 = 0;
    for (int x = 0; x<b.lblocknum.size(); x++){
        sum2 += b.lblockpsum[x];
    }
    for (int x = 1; x<b.lblocknum.size(); x++){
        //printf("blblock %d %d %d %d\n",b.lblocknum[x],b.lblockpos[x],b.lblockvals[x],b.lblockpsum[x]);
        t1 += b.lblocknum[x];
        t2 += b.lblockpsum[x-1];
        sum2 -= b.lblockpsum[x-1];
        t2 = min(t2,INF);
        bool added = false;
        while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
            t2 += a.rblockpsum[maxv];
            t2 = min(t2,INF);
            maxv++;
            added = true;
        }
        if (b.lblockvals[x]>t2){
            if (maxv==a.rblocknum.size()){
                if (ans.lblockpos.back()==a.len+b.lblockpos[x]){
                    ans.lblocknum.back()+=t1;
                }
                else{
                    ans.lblockpsum.back() -= sum2;
                    ans.lblockpos.push_back(a.len+b.lblockpos[x]);
                    ans.lblocknum.push_back(t1);
                    ans.lblockvals.push_back(b.lblockvals[x]);
                    ans.lblockpsum.push_back(sum2);
                }
            }
            t1 = 0;
        }
    }
    t2 += b.lblockpsum.back();
    while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
        t2 += a.rblockpsum[maxv];
        t2 = min(t2,INF);
        maxv++;
    }
    if (maxv==a.rblocknum.size()){
        ans.numfin += t1;
    }
    else{
        ans.rblocknum[ri] += t1;
    }
    assert(ans.lblocknum.size()==ans.lblockpos.size());
    assert(ans.lblockpos.size()==ans.lblockvals.size());
    assert(ans.lblockpsum.size()==ans.lblockvals.size());
    return ans;
}

int arr[100005];

struct node{
    int s,e;
    dat v;
    node *l,*r;
    node (int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            v = dat(arr[s]);
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            v = mer(l->v,r->v);
        //printf("node %d to %d has numfin %d\n",s,e,v.numfin);
        }
    }
    dat qu(int a, int b){
        //printf("node %d to %d, %d %d\n",s,e,a,b);
        if (a<=s && e<=b){
            return v;
        }
        if (b<=(s+e)/2){
            return l->qu(a,b);
        }
        if (a>(s+e)/2){
            return r->qu(a,b);
        }
        //printf("end %d %d\n",s,e);
        return mer(l->qu(a,b),r->qu(a,b));
    }
    void upd(int pos){
        if (s==e){
            v = dat(arr[s]);
            return;
        }
        if (pos<=(s+e)/2){
            l->upd(pos);
        }
        else{
            r->upd(pos);
        }
        v = mer(l->v,r->v);
    }
}*root;

 main(){
    int n;
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        scanf("%lld",&arr[x]);
    }
    root = new node(1,n);
    int q;
    scanf("%lld",&q);
    while (q--){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        if (a==1){
            arr[b] = c;
            root->upd(b);
        }
        else{
            printf("%lld\n",root->qu(b,c).numfin);
        }
    }
}

Compilation message (stderr)

fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int x = 0; x<a.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int x = 0; x<b.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int x = 0; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:85:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int x = 0; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:111:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int x = 0; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:114:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int x = 1; x<a.rblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:121:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
      |                ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:128:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             if (maxv==b.lblocknum.size()){
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:120:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
  120 |         bool added = false;
      |              ^~~~~
fish2.cpp:144:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:150:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     if (maxv==b.lblocknum.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:160:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int x = 0; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:163:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int x = 1; x<b.lblocknum.size(); x++){
      |                     ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:170:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
      |                ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:177:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             if (maxv==a.rblocknum.size()){
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:169:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
  169 |         bool added = false;
      |              ^~~~~
fish2.cpp:193:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:198:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     if (maxv==a.rblocknum.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp: At global scope:
fish2.cpp:258:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  258 |  main(){
      |  ^~~~
fish2.cpp: In function 'int main()':
fish2.cpp:260:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
fish2.cpp:262:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         scanf("%lld",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:266:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
fish2.cpp:269:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:202:25: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
  202 |         ans.rblocknum[ri] += t1;
      |                         ^
fish2.cpp:154:25: warning: 'li' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |         ans.lblocknum[li] += t1;
      |                         ^

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