oj.uz

Submission #447017

# Submission time Handle Problem Language Result Execution time Memory
447017 2021-07-24T08:40:22 Z zaneyu Fire (JOI20_ho_t5) C++14
14 / 100
 1000 ms 60364 KB 
/*input
20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<ll,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const ll maxn=4e5+5;
const ll maxlg=__lg(maxn)+2;
/** Interface */

inline int readChar();
template <class T = ll> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

template <class T> 
inline void writeInt(T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}

inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}

struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;
struct segt{
    ll seg[4*maxn],lazy[4*maxn];
    int n;
    void resize(int _n){
        n=_n;
    } 
    inline void pushdown(int idx,int l,int r){
        if(!lazy[idx]) return;
        seg[idx]+=(r-l+1)*lazy[idx];
        if(l==r){
            lazy[idx]=0;
            return;
        }
        lazy[idx<<1]+=lazy[idx];
        lazy[idx<<1|1]+=lazy[idx];
        lazy[idx]=0;
    }
    inline void upd(int idx,int l,int r,int ql,int qr,ll x){
        if(ql<=l and r<=qr){
            lazy[idx]+=x;
            return;
        }
        int mid=l+r>>1;
        if(qr<=mid) upd(idx<<1,l,mid,ql,qr,x);
        else if(ql>mid) upd(idx<<1|1,mid+1,r,ql,qr,x);
        else upd(idx<<1,l,mid,ql,qr,x),upd(idx<<1|1,mid+1,r,ql,qr,x);
        pushdown(idx<<1,l,mid),pushdown(idx<<1|1,mid+1,r);
        seg[idx]=(seg[idx<<1]+seg[idx<<1|1]);
    }
    inline ll query(int idx,int l,int r,int ql,int qr){
        pushdown(idx,l,r);
        if(ql<=l and r<=qr) return seg[idx];
        int mid=l+r>>1;
        if(qr<=mid) return query(idx<<1,l,mid,ql,qr);
        else if(ql>mid) return query(idx<<1|1,mid+1,r,ql,qr);
        return query(idx<<1,l,mid,ql,qr)+query(idx<<1|1,mid+1,r,ql,qr);
    }
    inline ll query(int l,int r){
        if(l>r) return 0;
        return query(1,0,n-1,l,r);
    }
    inline void upd(int l,int r,ll x){
        if(l>r) return;
        upd(1,0,n-1,l,r,x);
    }
}rect,par;
int n,q;
int arr[maxn];
ll ans[maxn];
vector<pair<pii,int>> upd[maxn];
vector<pair<pii,int>> query[maxn];
inline void tri(int l,int r,int v){
    if(l>r) return;
    //parallelogram-rectangle
    par.upd(l+n,2*n+1,v);
    rect.upd(r+n+1,2*n+1,-v);
    //place where xiao and da intersect
    if((r-l+1)<=n) upd[r-l+1].pb({{l,r},v});
}
int l[maxn],r[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    rect.resize(maxn),par.resize(maxn);
    n=readInt(),q=readInt();
    REP(i,n) arr[i]=readInt();
    vector<int> v;
    REP(i,n){
        while(sz(v) and arr[v.back()]<arr[i]) v.pop_back();
        if(sz(v)) l[i]=v.back();
        else l[i]=-n-1;
        v.pb(i);
    }
    v.clear();
    for(int i=n-1;i>=0;i--){
        while(sz(v) and arr[v.back()]<=arr[i]) v.pop_back();
        if(sz(v)) r[i]=v.back();
        else r[i]=n+1;
        v.pb(i);
    }
    REP(i,n){
        tri(l[i]+1,r[i]-1,arr[i]);
        tri(l[i]+1,i-1,-arr[i]);
        tri(i+1,r[i]-1,-arr[i]);
    }
    REP(i,q){
        int t=readInt(),l=readInt(),r=readInt();
        --l,--r;
        query[t].pb({{l,r},i});
    }
    REP1(i,n){
        for(auto x:upd[i]){
            int l=x.f.f,r=x.f.s,v=x.s;
            par.upd(l+n,2*n+1,-v);
            rect.upd(r+n+1,2*n+1,v);
        }
        for(auto x:query[i]){
            int l=x.f.f,r=x.f.s;
            ans[x.s]=par.query(l-i+n,r-i+n)+rect.query(l+n,r+n);
        }
    }
    REP(i,q) writeInt(ans[i],'\n');
}

Compilation message

ho_t5.cpp: In member function 'void segt::upd(int, int, int, int, int, ll)':
ho_t5.cpp:169:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |         int mid=l+r>>1;
      |                 ~^~
ho_t5.cpp: In member function 'll segt::query(int, int, int, int, int)':
ho_t5.cpp:179:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19204 KB Output is correct
2 Correct 11 ms 19276 KB Output is correct
3 Correct 11 ms 19276 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 11 ms 19400 KB Output is correct
6 Correct 11 ms 19388 KB Output is correct
7 Correct 13 ms 19376 KB Output is correct
8 Correct 14 ms 19276 KB Output is correct
9 Correct 11 ms 19276 KB Output is correct
10 Correct 12 ms 19284 KB Output is correct
11 Correct 11 ms 19328 KB Output is correct
12 Correct 11 ms 19276 KB Output is correct
13 Correct 11 ms 19320 KB Output is correct
14 Correct 11 ms 19276 KB Output is correct
15 Correct 11 ms 19364 KB Output is correct
16 Correct 12 ms 19324 KB Output is correct
17 Correct 12 ms 19276 KB Output is correct
18 Correct 11 ms 19276 KB Output is correct
19 Correct 12 ms 19404 KB Output is correct
20 Correct 11 ms 19396 KB Output is correct
21 Correct 11 ms 19276 KB Output is correct
22 Correct 11 ms 19312 KB Output is correct
23 Correct 12 ms 19276 KB Output is correct
24 Correct 11 ms 19276 KB Output is correct
25 Correct 12 ms 19276 KB Output is correct
26 Correct 12 ms 19276 KB Output is correct
27 Correct 12 ms 19276 KB Output is correct
28 Correct 11 ms 19276 KB Output is correct
29 Correct 11 ms 19276 KB Output is correct
30 Correct 12 ms 19276 KB Output is correct
31 Correct 11 ms 19320 KB Output is correct
32 Correct 11 ms 19276 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19204 KB Output is correct
2 Correct 963 ms 60364 KB Output is correct
3 Correct 965 ms 57156 KB Output is correct
4 Execution timed out 1004 ms 57464 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19204 KB Output is correct
2 Correct 900 ms 57684 KB Output is correct
3 Correct 971 ms 57156 KB Output is correct
4 Correct 949 ms 58580 KB Output is correct
5 Correct 982 ms 57356 KB Output is correct
6 Correct 853 ms 57720 KB Output is correct
7 Correct 930 ms 57864 KB Output is correct
8 Correct 966 ms 57868 KB Output is correct
9 Correct 873 ms 57352 KB Output is correct
10 Correct 900 ms 56908 KB Output is correct
11 Correct 984 ms 58380 KB Output is correct
12 Correct 924 ms 58140 KB Output is correct
13 Correct 918 ms 58204 KB Output is correct
14 Correct 925 ms 57508 KB Output is correct
15 Correct 935 ms 58356 KB Output is correct
16 Correct 943 ms 57884 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 57452 KB Output is correct
2 Correct 842 ms 57528 KB Output is correct
3 Correct 924 ms 58528 KB Output is correct
4 Correct 831 ms 57304 KB Output is correct
5 Correct 898 ms 57528 KB Output is correct
6 Correct 912 ms 57776 KB Output is correct
7 Correct 917 ms 58408 KB Output is correct
8 Correct 962 ms 58004 KB Output is correct
9 Correct 867 ms 57688 KB Output is correct
10 Correct 919 ms 58132 KB Output is correct
11 Correct 891 ms 57928 KB Output is correct
12 Correct 942 ms 58064 KB Output is correct
13 Correct 848 ms 57740 KB Output is correct
14 Correct 872 ms 57724 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19204 KB Output is correct
2 Correct 11 ms 19276 KB Output is correct
3 Correct 11 ms 19276 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 11 ms 19400 KB Output is correct
6 Correct 11 ms 19388 KB Output is correct
7 Correct 13 ms 19376 KB Output is correct
8 Correct 14 ms 19276 KB Output is correct
9 Correct 11 ms 19276 KB Output is correct
10 Correct 12 ms 19284 KB Output is correct
11 Correct 11 ms 19328 KB Output is correct
12 Correct 11 ms 19276 KB Output is correct
13 Correct 11 ms 19320 KB Output is correct
14 Correct 11 ms 19276 KB Output is correct
15 Correct 11 ms 19364 KB Output is correct
16 Correct 12 ms 19324 KB Output is correct
17 Correct 12 ms 19276 KB Output is correct
18 Correct 11 ms 19276 KB Output is correct
19 Correct 12 ms 19404 KB Output is correct
20 Correct 11 ms 19396 KB Output is correct
21 Correct 11 ms 19276 KB Output is correct
22 Correct 11 ms 19312 KB Output is correct
23 Correct 12 ms 19276 KB Output is correct
24 Correct 11 ms 19276 KB Output is correct
25 Correct 12 ms 19276 KB Output is correct
26 Correct 12 ms 19276 KB Output is correct
27 Correct 12 ms 19276 KB Output is correct
28 Correct 11 ms 19276 KB Output is correct
29 Correct 11 ms 19276 KB Output is correct
30 Correct 12 ms 19276 KB Output is correct
31 Correct 11 ms 19320 KB Output is correct
32 Correct 11 ms 19276 KB Output is correct
33 Correct 963 ms 60364 KB Output is correct
34 Correct 965 ms 57156 KB Output is correct
35 Execution timed out 1004 ms 57464 KB Time limit exceeded
36 Halted 0 ms 0 KB -