oj.uz

Submission #398196

# Submission time Handle Problem Language Result Execution time Memory
398196 2021-05-03T22:40:13 Z duality Fire (JOI20_ho_t5) C++11
1 / 100
 1000 ms 59368 KB 
#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 ----------
#pragma GCC optimize("Ofast")

int S[200000],l[200000],r[200000];
LLI ans[200000];
struct event { int y,l,r,t,i; };
bool comp(event a,event b) {
    if (a.y == b.y) return abs(a.t) > abs(b.t);
    else return a.y < b.y;
}
vector<event> v1,v2;
vi s;
LLI tree[1 << 20],lazy[1 << 20];
int prop(int s,int e,int i) {
    tree[i] += lazy[i]*(e-s+1);
    if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
    lazy[i] = 0;
    return 0;
}
int update(int s,int e,int as,int ae,int i,int num) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        lazy[i] += num;
        prop(s,e,i);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,num),update(mid+1,e,as,ae,2*i+2,num);
    tree[i] = tree[2*i+1] + tree[2*i+2];
    return 0;
}
LLI query(int s,int e,int qs,int qe,int i) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return 0;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return query(s,mid,qs,qe,2*i+1)+query(mid+1,e,qs,qe,2*i+2);
}
int main() {
    int i;
    int N,Q,T,L,R;
    scanf("%d %d",&N,&Q);
    for (i = 0; i < N; i++) scanf("%d",&S[i]);
    for (i = 0; i < Q; i++) {
        scanf("%d %d %d",&T,&L,&R);
        L--,R--;
        v1.pb((event){T,L,R,0,i});
        v2.pb((event){T,L-T,R-T,0,i});
    }

    for (i = 0; i < N; i++) {
        while (!s.empty() && (S[s.back()] < S[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() && (S[s.back()] <= S[i])) s.pop_back();
        if (s.empty()) r[i] = N;
        else r[i] = s.back();
        s.pb(i);
    }
    for (i = 0; i < N; i++) {
        v1.pb((event){r[i]-i,i,r[i]-1,S[i],0});
        v1.pb((event){0,i,N,S[i],0});
        v1.pb((event){r[i]-i,i,N,-S[i],0});
        v2.pb((event){0,i+1,N,-S[i],0});
        v2.pb((event){r[i]-i,i+1,N,S[i],0});
        if (l[i] != -1) {
            v1.pb((event){r[i]-l[i]-1,i,r[i]-1,-S[i],0});
            v1.pb((event){i-l[i],i,N,-S[i],0});
            v1.pb((event){r[i]-l[i]-1,i,N,S[i],0});
            v2.pb((event){i-l[i],l[i]+1,N,S[i],0});
            v2.pb((event){r[i]-l[i]-1,l[i]+1,N,-S[i],0});
        }
    }
    sort(v1.begin(),v1.end(),comp);
    sort(v2.begin(),v2.end(),comp);
    for (i = 0; i < v1.size(); i++) {
        if (v1[i].t != 0) update(0,2*N,v1[i].l+N,v1[i].r+N,0,v1[i].t);
        else ans[v1[i].i] += query(0,2*N,v1[i].l+N,v1[i].r+N,0);
    }
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof(lazy));
    for (i = 0; i < v2.size(); i++) {
        if (v2[i].t != 0) update(0,2*N,v2[i].l+N,v2[i].r+N,0,v2[i].t);
        else ans[v2[i].i] += query(0,2*N,v2[i].l+N,v2[i].r+N,0);
    }
    for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);

    return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (i = 0; i < v1.size(); i++) {
      |                 ~~^~~~~~~~~~~
ho_t5.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (i = 0; i < v2.size(); i++) {
      |                 ~~^~~~~~~~~~~
ho_t5.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d %d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:101:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |     for (i = 0; i < N; i++) scanf("%d",&S[i]);
      |                             ~~~~~^~~~~~~~~~~~
ho_t5.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf("%d %d %d",&T,&L,&R);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16844 KB Output is correct
5 Correct 9 ms 16716 KB Output is correct
6 Correct 9 ms 16840 KB Output is correct
7 Correct 9 ms 16736 KB Output is correct
8 Correct 9 ms 16844 KB Output is correct
9 Correct 9 ms 16716 KB Output is correct
10 Correct 9 ms 16844 KB Output is correct
11 Correct 8 ms 16772 KB Output is correct
12 Correct 8 ms 16808 KB Output is correct
13 Correct 9 ms 16716 KB Output is correct
14 Correct 9 ms 16736 KB Output is correct
15 Correct 9 ms 16716 KB Output is correct
16 Correct 9 ms 16716 KB Output is correct
17 Correct 8 ms 16844 KB Output is correct
18 Correct 8 ms 16716 KB Output is correct
19 Correct 8 ms 16836 KB Output is correct
20 Correct 9 ms 16716 KB Output is correct
21 Correct 8 ms 16716 KB Output is correct
22 Correct 8 ms 16844 KB Output is correct
23 Correct 9 ms 16776 KB Output is correct
24 Correct 9 ms 16716 KB Output is correct
25 Correct 9 ms 16764 KB Output is correct
26 Correct 9 ms 16840 KB Output is correct
27 Correct 9 ms 16844 KB Output is correct
28 Correct 10 ms 16716 KB Output is correct
29 Correct 11 ms 16808 KB Output is correct
30 Correct 9 ms 16844 KB Output is correct
31 Correct 10 ms 16716 KB Output is correct
32 Correct 9 ms 16716 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Execution timed out 1095 ms 58652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Execution timed out 1085 ms 58672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 59368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16844 KB Output is correct
5 Correct 9 ms 16716 KB Output is correct
6 Correct 9 ms 16840 KB Output is correct
7 Correct 9 ms 16736 KB Output is correct
8 Correct 9 ms 16844 KB Output is correct
9 Correct 9 ms 16716 KB Output is correct
10 Correct 9 ms 16844 KB Output is correct
11 Correct 8 ms 16772 KB Output is correct
12 Correct 8 ms 16808 KB Output is correct
13 Correct 9 ms 16716 KB Output is correct
14 Correct 9 ms 16736 KB Output is correct
15 Correct 9 ms 16716 KB Output is correct
16 Correct 9 ms 16716 KB Output is correct
17 Correct 8 ms 16844 KB Output is correct
18 Correct 8 ms 16716 KB Output is correct
19 Correct 8 ms 16836 KB Output is correct
20 Correct 9 ms 16716 KB Output is correct
21 Correct 8 ms 16716 KB Output is correct
22 Correct 8 ms 16844 KB Output is correct
23 Correct 9 ms 16776 KB Output is correct
24 Correct 9 ms 16716 KB Output is correct
25 Correct 9 ms 16764 KB Output is correct
26 Correct 9 ms 16840 KB Output is correct
27 Correct 9 ms 16844 KB Output is correct
28 Correct 10 ms 16716 KB Output is correct
29 Correct 11 ms 16808 KB Output is correct
30 Correct 9 ms 16844 KB Output is correct
31 Correct 10 ms 16716 KB Output is correct
32 Correct 9 ms 16716 KB Output is correct
33 Execution timed out 1095 ms 58652 KB Time limit exceeded
34 Halted 0 ms 0 KB -