Submission #396893

#	Time	Username	Problem	Language	Result	Execution time	Memory
396893		duality	Dungeon 3 (JOI21_ho_t5)	C++11	100 / 100	3289 ms	573196 KiB

Main

#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int N;
int A[200000],B[200000],S[200000],T[200000],U[200000];
LLI pre[200001];
int l[200000],r[200000];
vi s;
int sparse[200000][18],logg[200001];
pii sparse2[200000][18];
int query(int s,int e) {
    int l = logg[e-s+1];
    return max(sparse[s][l],sparse[e-(1 << l)+1][l]);
}
int query2(int s,int e) {
    int l = logg[e-s+1];
    return min(sparse2[s][l],sparse2[e-(1 << l)+1][l]).second;
}
LLI ans[200000];
vpii queries;
struct event {
    int l,r,w;
    LLI x;
};
vector<event> events;
bool comp(event a,event b) {
    return a.x < b.x;
}
LLI bit[200001];
struct data {
    vector<pair<pii,LLI> > vv;
    int update(int i,LLI num) {
        vv.pb(mp(mp(i,-1),num));
        return 0;
    }
    int query(int i,int a,LLI w) {
        vv.pb(mp(mp(i,a),w));
        return 0;
    }
    int process() {
        int i,j;
        for (i = 0; i < vv.size(); i++) {
            if (vv[i].first.second == -1) {
                for (j = vv[i].first.first+1; j <= N; j += j & (-j)) bit[j] += vv[i].second;
            }
            else {
                for (j = vv[i].first.first+1; j > 0; j -= j & (-j)) ans[vv[i].first.second] += vv[i].second*bit[j];
            }
        }
        for (i = 0; i < vv.size(); i++) {
            if (vv[i].first.second == -1) {
                for (j = vv[i].first.first+1; j <= N; j += j & (-j)) bit[j] = 0;
            }
        }
        vv.clear();
        return 0;
    }
};
data bit1[200001],bit2[200001];
int parent[200000][18],logn;
int parent2[200000][18];
int disc[200000],fin[200000],num = 0;
vi adjList[200000];
int doDFS(int u) {
    int i;
    disc[u] = num++;
    for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
    fin[u] = num;
    return 0;
}
LLI sum[200000],sum2[200000],sum3[200000];
int main() {
    int i;
    int M;
    scanf("%d %d",&N,&M);
    for (i = 0; i < N; i++) scanf("%d",&A[i]),pre[i+1] = pre[i]+A[i];
    for (i = 0; i < N; i++) scanf("%d",&B[i]);
    for (i = 0; i < M; i++) scanf("%d %d %d",&S[i],&T[i],&U[i]),S[i]--,T[i] -= 2;

    int j;
    for (i = 0; i < N; i++) {
        while (!s.empty() && (B[s.back()] > B[i])) s.pop_back();
        if (s.empty()) l[i] = -1;
        else l[i] = s.back();
        s.pb(i);
    }
    s.clear();
    for (i = N-1; i >= 0; i--) {
        while (!s.empty() && (B[s.back()] >= B[i])) s.pop_back();
        if (s.empty()) r[i] = N;
        else r[i] = s.back();
        s.pb(i);
    }
    for (i = 0; i < N; i++) sparse[i][0] = A[i],sparse2[i][0] = mp(B[i],i);
    for (i = 1; (1 << i) <= N; i++) {
        for (j = 0; j <= N-(1 << i); j++) {
            sparse[j][i] = max(sparse[j][i-1],sparse[j+(1 << (i-1))][i-1]);
            sparse2[j][i] = min(sparse2[j][i-1],sparse2[j+(1 << (i-1))][i-1]);
        }
    }
    for (i = 2; i <= N; i++) logg[i] = logg[i/2]+1;
    for (i = 0; i < N; i++) parent[i][0] = l[i];
    for (i = 1; (1 << i) < N; i++) {
        for (j = 0; j < N; j++) {
            if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
            else parent[j][i] = -1;
        }
    }
    for (i = N-1; i >= 0; i--) parent2[i][0] = r[i];
    for (i = 1; (1 << i) < N; i++) {
        for (j = 0; j < N; j++) {
            if (parent2[j][i-1] != N) parent2[j][i] = parent2[parent2[j][i-1]][i-1];
            else parent2[j][i] = N;
        }
    }
    logn = i;

    int k;
    for (i = 0; i < M; i++) {
        if (query(S[i],T[i]) > U[i]) ans[i] = -1;
        else queries.pb(mp(U[i],i));
    }
    sort(queries.begin(),queries.end());
    for (i = 0; i < N; i++) {
        if ((l[i] >= 0) && (r[i] < N)) {
            events.pb((event){l[i],r[i],-B[i],pre[r[i]]-pre[l[i]]});
            events.pb((event){l[i],r[i],B[i],pre[r[i]]-pre[i]});
            events.pb((event){l[i],r[i],B[i],pre[i]-pre[l[i]]});
        }
    }
    sort(events.begin(),events.end(),comp);
    for (i = 0; i < events.size(); i++) {
        for (k = events[i].l+1; k > 0; k -= k & (-k)) bit2[k].update(events[i].r,events[i].w);
    }
    j = 0;
    for (i = 0; i < queries.size(); i++) {
        while ((j < events.size()) && (events[j].x < queries[i].first)) {
            for (k = events[j].l+1; k > 0; k -= k & (-k)) {
                bit2[k].update(events[j].r,-events[j].w);
                bit1[k].update(events[j].r,events[j].x*events[j].w);
            }
            j++;
        }
        for (k = S[queries[i].second]+1; k <= N; k += k & (-k)) {
            bit1[k].query(T[queries[i].second],queries[i].second,1);
            bit2[k].query(T[queries[i].second],queries[i].second,queries[i].first);
        }
    }
    for (i = 0; i <= N; i++) bit1[i].process(),bit2[i].process();

    for (i = 0; i < N; i++) {
        if (r[i] != N) adjList[r[i]].pb(i);
    }
    for (i = 0; i < N; i++) {
        if (r[i] == N) doDFS(i);
    }
    events.clear();
    for (i = 0; i < N; i++) {
        if (r[i] < N) events.pb((event){i,i,B[i],pre[r[i]]-pre[i]});
    }
    sort(events.begin(),events.end(),comp);
    for (i = 0; i < events.size(); i++) {
        bit2[0].update(disc[events[i].l],events[i].w);
        bit2[0].update(fin[events[i].l],-events[i].w);
    }
    j = 0;
    for (i = 0; i < queries.size(); i++) {
        while ((j < events.size()) && (events[j].x < queries[i].first)) {
            bit2[0].update(disc[events[j].l],-events[j].w);
            bit2[0].update(fin[events[j].l],events[j].w);
            bit1[0].update(disc[events[j].l],events[j].x*events[j].w);
            bit1[0].update(fin[events[j].l],-events[j].x*events[j].w);
            j++;
        }

        bit1[0].query(disc[S[queries[i].second]],queries[i].second,1);
        bit2[0].query(disc[S[queries[i].second]],queries[i].second,queries[i].first);
        int u = S[queries[i].second];
        for (k = logn-1; k >= 0; k--) {
            if (parent2[u][k] <= T[queries[i].second]) u = parent2[u][k];
        }
        bit1[0].query(disc[u],queries[i].second,-1);
        bit2[0].query(disc[u],queries[i].second,-queries[i].first);
    }
    bit1[0].process(),bit2[0].process();
    num = 0;
    for (i = 0; i < N; i++) adjList[i].clear();
    for (i = 0; i < N; i++) {
        if (l[i] != -1) adjList[l[i]].pb(i);
    }
    for (i = 0; i < N; i++) {
        if (l[i] == -1) doDFS(i);
    }
    events.clear();
    for (i = 0; i < N; i++) {
        if (l[i] >= 0) events.pb((event){i,i,B[i],pre[i]-pre[l[i]]});
    }
    sort(events.begin(),events.end(),comp);
    for (i = 0; i < events.size(); i++) {
        bit2[0].update(disc[events[i].l],events[i].w);
        bit2[0].update(fin[events[i].l],-events[i].w);
    }
    j = 0;
    for (i = 0; i < queries.size(); i++) {
        while ((j < events.size()) && (events[j].x < queries[i].first)) {
            bit2[0].update(disc[events[j].l],-events[j].w);
            bit2[0].update(fin[events[j].l],events[j].w);
            bit1[0].update(disc[events[j].l],events[j].x*events[j].w);
            bit1[0].update(fin[events[j].l],-events[j].x*events[j].w);
            j++;
        }

        bit1[0].query(disc[T[queries[i].second]],queries[i].second,1);
        bit2[0].query(disc[T[queries[i].second]],queries[i].second,queries[i].first);
        int u = T[queries[i].second];
        for (k = logn-1; k >= 0; k--) {
            if (parent[u][k] >= S[queries[i].second]) u = parent[u][k];
        }
        bit1[0].query(disc[u],queries[i].second,-1);
        bit2[0].query(disc[u],queries[i].second,-queries[i].first);
    }
    bit1[0].process(),bit2[0].process();
    for (i = 0; i < N; i++) {
        sum[i] = pre[i],sum2[i] = B[i],sum3[i] = pre[i]*B[i];
        if (l[i] != -1) {
            sum[i] += sum[l[i]];
            sum2[i] += sum2[l[i]];
            sum3[i] += sum3[l[i]];
        }
    }
    for (i = 0; i < M; i++) {
        if (query(S[i],T[i]) <= U[i]) {
            int u = T[i];
            for (j = logn-1; j >= 0; j--) {
                if ((parent[u][j] >= S[i]) && (pre[T[i]+1]-pre[parent[u][j]] < U[i])) {
                    ans[i] += (sum2[u]-sum2[parent[u][j]])*pre[T[i]+1];
                    ans[i] -= sum3[u]-sum3[parent[u][j]];
                    u = parent[u][j];
                }
            }
            while ((parent[u][0] >= S[i]) && (pre[T[i]+1]-pre[u] < U[i])) {
                ans[i] += (sum2[u]-sum2[parent[u][0]])*pre[T[i]+1];
                ans[i] -= sum3[u]-sum3[parent[u][0]];
                u = parent[u][0];
            }
            for (j = logn-1; j >= 0; j--) {
                if (parent[u][j] >= S[i]) {
                    ans[i] += (sum2[u]-sum2[parent[u][j]])*U[i];
                    u = parent[u][j];
                }
            }
            j = query2(S[i],T[i]);
            LLI b = min(pre[T[i]+1]-pre[j],(LLI) U[i]);
            ans[i] += b*B[j];
        }
    }
    for (i = 0; i < N; i++) {
        if (l[i] != -1) {
            sum[i] = pre[l[i]],sum2[i] = B[i],sum3[i] = pre[l[i]]*B[i];
            sum[i] += sum[l[i]];
            sum2[i] += sum2[l[i]];
            sum3[i] += sum3[l[i]];
        }
        else sum[i] = sum2[i] = sum3[i] = 0;
    }
    for (i = 0; i < M; i++) {
        if (query(S[i],T[i]) <= U[i]) {
            int u = T[i];
            for (j = logn-1; j >= 0; j--) {
                if ((parent[u][j] >= S[i]) && (l[parent[u][j]] >= S[i]) && (pre[T[i]+1]-pre[l[parent[u][j]]] < U[i])) {
                    ans[i] -= (sum2[u]-sum2[parent[u][j]])*pre[T[i]+1];
                    ans[i] += sum3[u]-sum3[parent[u][j]];
                    u = parent[u][j];
                }
            }
            while ((parent[u][0] >= S[i]) && (pre[T[i]+1]-pre[l[u]] < U[i])) {
                ans[i] -= (sum2[u]-sum2[parent[u][0]])*pre[T[i]+1];
                ans[i] += sum3[u]-sum3[parent[u][0]];
                u = parent[u][0];
            }
            for (j = logn-1; j >= 0; j--) {
                if (parent[u][j] >= S[i]) {
                    ans[i] -= (sum2[u]-sum2[parent[u][j]])*U[i];
                    u = parent[u][j];
                }
            }
        }
    }
    for (i = 0; i < M; i++) printf("%lld\n",ans[i]);

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'int data::process()':
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
Main.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
Main.cpp: In function 'int doDFS(int)':
Main.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i]);
      |                 ~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:186:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (i = 0; i < events.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:190:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for (i = 0; i < queries.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
Main.cpp:191:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         while ((j < events.size()) && (events[j].x < queries[i].first)) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for (i = 0; i < events.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:221:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |     for (i = 0; i < queries.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
Main.cpp:222:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         while ((j < events.size()) && (events[j].x < queries[i].first)) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:253:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |     for (i = 0; i < events.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:258:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |     for (i = 0; i < queries.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
Main.cpp:259:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |         while ((j < events.size()) && (events[j].x < queries[i].first)) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:130:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |     for (i = 0; i < N; i++) scanf("%d",&A[i]),pre[i+1] = pre[i]+A[i];
      |                             ~~~~~^~~~~~~~~~~~
Main.cpp:131:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |     for (i = 0; i < N; i++) scanf("%d",&B[i]);
      |                             ~~~~~^~~~~~~~~~~~
Main.cpp:132:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |     for (i = 0; i < M; i++) scanf("%d %d %d",&S[i],&T[i],&U[i]),S[i]--,T[i] -= 2;
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44