API tools faq
paste
View difference between Paste ID: RKR2Vg3X and NReiwJG4
SHOW: | | - or go back to the newest paste.
1-
#include <bits/stdc++.h>
1+
#include <bits/stdc++.h>
2-
2+
3-
#pragma GCC optimize("Ofast")
3+
#pragma GCC optimize("Ofast")

4-
#pragma GCC optimize("O3")
4+
#pragma GCC optimize("O3")

5-
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
5+
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

6-
using namespace std;
6+
using namespace std;

7-
typedef long long ll;
7+
typedef long long ll;

8-
typedef long double ld;
8+
typedef long double ld;

9-
9+
10-
/*
10+
/*

11-
⣿⣿⣷⡁⢆⠈⠕⢕⢂⢕⢂⢕⢂⢔⢂⢕⢄⠂⣂⠂⠆⢂⢕⢂⢕⢂⢕⢂⢕⢂
11+
⣿⣿⣷⡁⢆⠈⠕⢕⢂⢕⢂⢕⢂⢔⢂⢕⢄⠂⣂⠂⠆⢂⢕⢂⢕⢂⢕⢂⢕⢂

12-
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕
12+
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕

13-
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂
13+
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂

14-
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂
14+
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂

15-
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔
15+
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔

16-
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿
16+
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿

17-
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿
17+
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿

18-
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃
18+
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃

19-
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈
19+
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈

20-
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈
20+
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈

21-
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈
21+
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈

22-
⠄⠁⠕⢝⡢⠈⠻⣿⣿⣿⣿⣿⣿⣿⣷⣕⣑⣑⣑⣵⣿⣿⣿⡿⢋⢔⢕⣿⠠⠈
22+
⠄⠁⠕⢝⡢⠈⠻⣿⣿⣿⣿⣿⣿⣿⣷⣕⣑⣑⣑⣵⣿⣿⣿⡿⢋⢔⢕⣿⠠⠈

23-
⠨⡂⡀⢑⢕⡅⠂⠄⠉⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢔⢕⢕⣿⣿⠠⠈
23+
⠨⡂⡀⢑⢕⡅⠂⠄⠉⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢔⢕⢕⣿⣿⠠⠈

24-
⠄⠪⣂⠁⢕⠆⠄⠂⠄⠁⡀⠂⡀⠄⢈⠉⢍⢛⢛⢛⢋⢔⢕⢕⢕⣽⣿⣿⠠⠈
24+
⠄⠪⣂⠁⢕⠆⠄⠂⠄⠁⡀⠂⡀⠄⢈⠉⢍⢛⢛⢛⢋⢔⢕⢕⢕⣽⣿⣿⠠⠈

25-
*/
25+
*/

26-
#define all(a) a.begin(), a.end()
26+
#define all(a) a.begin(), a.end()

27-
#define FNAME ""
27+
#define FNAME ""

28-
//#define int ll
28+
//#define int ll

29-
typedef pair<int, int> pii;
29+
typedef pair<int, int> pii;

30-
#define _ << ' ' <<
30+
#define _ << ' ' <<

31-
#define vec vector
31+
#define vec vector

32-
#ifndef HOME
32+
#ifndef HOME

33-
#define cerr \
33+
#define cerr \

34-
    if (0) cerr
34+
    if (0) cerr

35-
#endif
35+
#endif

36-
36+
37-
bool chkmax(int &a, int b, bool eq = false) {
37+
const int max_memory = 1e8;

38-
    if (a < b) {
38+
39-
        a = b;
39+
int pos_memory = 0;

40-
        return true;
40+
char memory[max_memory];

41-
    }
41+
42-
    return a == b && eq;
42+
void* operator new(size_t n) {

43
    char *res = memory + pos_memory;

44-
bool chkmin(int &a, int b, bool eq = false) {
44+
    pos_memory += n;

45-
    if (a > b) {
45+
    assert(pos_memory <= max_memory);

46-
        a = b;
46+
    return (void*) res;

47-
        return true;
47+
}

48-
    }
48+
void operator delete(void *){}

49-
    return a == b && eq;
49+
50
bool chkmax(int &a, int b, bool eq = false) {

51-
#ifdef int
51+
    if (a < b) {

52-
const int INF = 2e16;
52+
        a = b;

53-
#else
53+
        return true;

54-
const int INF = 2e9;
54+
    }

55-
#endif
55+
    return a == b && eq;

56-
56+
}

57-
mt19937 gen(time(0));
57+
bool chkmin(int &a, int b, bool eq = false) {

58-
const int MAXN = 1e5 + 123;
58+
    if (a > b) {

59-
//set<int> st;
59+
        a = b;

60-
struct Node {
60+
        return true;

61-
    int l, r;
61+
    }

62-
    int ind;
62+
    return a == b && eq;

63-
};
63+
}

64-
Node nd[MAXN];
64+
#ifdef int

65-
int rest[MAXN];
65+
const int INF = 2e16;

66-
int lst = 1;
66+
#else

67-
int nn() {
67+
const int INF = 2e9;

68-
    return lst++;
68+
#endif

69
70-
int f[MAXN];
70+
mt19937 gen(time(0));

71-
int lf[MAXN];
71+
const int MAXN = 1e5 + 123;

72-
int rg[MAXN];
72+
//set<int> st;

73-
int a[MAXN];
73+
struct Node {

74-
void solve() {
74+
    int l, r;

75-
    //code here
75+
    int ind;

76-
    int n, k;
76+
};

77-
    cin >> n >> k;
77+
Node nd[MAXN];

78-
    
78+
int rest[MAXN];

79-
    vec<pii> vc;
79+
int lst = 1;

80-
    vc.resize(n);
80+
int nn() {

81-
    int pos = 0;
81+
    return lst++;

82-
    for (int i = 0; i < n; ++i) {
82+
}

83-
        int x;
83+
int f[MAXN];

84-
        cin >> x;
84+
int lf[MAXN];

85-
        a[i + 1] = x;
85+
int rg[MAXN];

86-
        vc[pos++]={-x, i + 1};
86+
int a[MAXN];

87-
    }
87+
void solve() {

88-
    {
88+
    //code here

89-
        stack<pii> st;
89+
    int n, k;

90-
        st.push({INF, -1});
90+
    cin >> n >> k;

91-
        for (int i = 1; i <= n; ++i) {
91+
92-
            while (st.top().first < a[i]) {
92+
    vec<pii> vc;

93-
                st.pop();
93+
    vc.resize(n);

94-
            }
94+
    int pos = 0;

95-
            lf[i] = st.top().second;
95+
    for (int i = 0; i < n; ++i) {

96-
            st.push({a[i], i});
96+
        int x;

97-
        }
97+
        cin >> x;

98-
        
98+
        a[i + 1] = x;

99-
    }
99+
        vc[pos++]={-x, i + 1};

100-
    {
100+
    }

101-
        stack<pii> st;
101+
    {

102-
        st.push({INF, -1});
102+
        stack<pii> st;

103-
        for (int i = n; i >= 1; --i) {
103+
        st.push({INF, -1});

104-
            while (st.top().first <= a[i]) {
104+
        for (int i = 1; i <= n; ++i) {

105-
                st.pop();
105+
            while (st.top().first < a[i]) {

106-
            }
106+
                st.pop();

107-
            rg[i] = st.top().second;
107+
            }

108-
            st.push({a[i], i});
108+
            lf[i] = st.top().second;

109-
        }
109+
            st.push({a[i], i});

110-
        
110+
        }

111-
    }
111+
112-
    sort(all(vc));
112+
    }

113-
    ll ans =0 ;
113+
    {

114-
    
114+
        stack<pii> st;

115-
    for (auto [X, i]: vc) {
115+
        st.push({INF, -1});

116-
        X = -X;
116+
        for (int i = n; i >= 1; --i) {

117-
//        st.insert(i);
117+
            while (st.top().first <= a[i]) {

118-
        int ind = nn();
118+
                st.pop();

119-
        rest[i] = ind;
119+
            }

120-
        if (lf[i] != -1) {
120+
            rg[i] = st.top().second;

121-
            int l = rest[lf[i]];
121+
            st.push({a[i], i});

122-
            nd[ind].l = l;
122+
        }

123-
            nd[l].r = ind;
123+
124-
        } else {
124+
    }

125-
            nd[ind].l = -1;
125+
    sort(all(vc));

126-
        }
126+
    ll ans =0 ;

127-
        if (rg[i] != -1) {
127+
128-
            int r = rest[rg[i]];
128+
    for (auto [X, i]: vc) {

129-
            nd[ind].r = r;
129+
        X = -X;

130-
            nd[r].l = ind;
130+
//        st.insert(i);

131-
        } else {
131+
        int ind = nn();

132-
            nd[ind].r = -1;
132+
        rest[i] = ind;

133-
        }
133+
        if (lf[i] != -1) {

134-
        nd[ind].ind = i;
134+
            int l = rest[lf[i]];

135-
//        for (int i = 0; i < 2 * k + 10; ++i) {
135+
            nd[ind].l = l;

136-
//            f[i] = -1;
136+
            nd[l].r = ind;

137-
//        }
137+
        } else {

138-
        //TODO переписать эту хрень на двусвязный список
138+
            nd[ind].l = -1;

139-
        int fi= k + 1;
139+
        }

140-
        f[k] = i;
140+
        if (rg[i] != -1) {

141-
        int indf = nd[ind].r;
141+
            int r = rest[rg[i]];

142-
        for (int j = 0; j < k - 1; ++j) {
142+
            nd[ind].r = r;

143-
            if (indf == -1) break;
143+
            nd[r].l = ind;

144-
            f[fi++] = (nd[indf].ind);
144+
        } else {

145-
            indf= nd[indf].r;
145+
            nd[ind].r = -1;

146-
        }
146+
        }

147-
        
147+
        nd[ind].ind = i;

148-
        if (indf == -1) {
148+
//        for (int i = 0; i < 2 * k + 10; ++i) {

149-
            f[fi]=n + 1;
149+
//            f[i] = -1;

150-
        } else {
150+
//        }

151-
            f[fi]= (nd[indf].ind);
151+
        //TODO переписать эту хрень на двусвязный список

152-
        }
152+
        int fi= k + 1;

153-
        int forw = fi --;
153+
        f[k] = i;

154-
        
154+
        int indf = nd[ind].r;

155-
        fi = k - 1;
155+
        for (int j = 0; j < k - 1; ++j) {

156-
        for (int j = 0; j < k - 1; ++j) {
156+
            if (indf == -1) break;

157-
            if (nd[ind].l == -1) break;
157+
            f[fi++] = (nd[indf].ind);

158-
            ind = nd[ind].l;
158+
            indf= nd[indf].r;

159-
            f[fi--] = (nd[ind].ind);
159+
        }

160-
        }
160+
161-
        
161+
        if (indf == -1) {

162-
        int back = fi + 1;
162+
            f[fi]=n + 1;

163-
        if (nd[ind].l == -1 ) {
163+
        } else {

164-
            f[fi] = 0;
164+
            f[fi]= (nd[indf].ind);

165-
        } else {
165+
        }

166-
            ind = nd[ind].l;
166+
        int forw = fi --;

167-
            f[fi] = nd[ind].ind;
167+
168-
        }
168+
        fi = k - 1;

169-
        forw = min(forw - k, k);
169+
        for (int j = 0; j < k - 1; ++j) {

170-
        for (int i = back; i <= forw; ++i) {
170+
            if (nd[ind].l == -1) break;

171-
            int j = i + k;
171+
            ind = nd[ind].l;

172-
            int c = f[i] - f[i - 1];
172+
            f[fi--] = (nd[ind].ind);

173-
            int d = f[j] - f[j - 1];
173+
        }

174-
            ans += 1ll * c * d * X;
174+
175-
        }
175+
        int back = fi + 1;

176-
    }
176+
        if (nd[ind].l == -1 ) {

177-
    cout << ans;
177+
            f[fi] = 0;

178-
    //
178+
        } else {

179
            ind = nd[ind].l;

180-
signed main() {
180+
            f[fi] = nd[ind].ind;

181-
#ifdef HOME
181+
        }

182-
    freopen("input.txt", "r", stdin);
182+
        forw = min(forw - k, k);

183-
    //freopen("input.txt", "w", stdout);
183+
        for (int i = back; i <= forw; ++i) {

184-
#else
184+
            int j = i + k;

185-
    if (FNAME != "") {
185+
            int c = f[i] - f[i - 1];

186-
        freopen(FNAME ".in", "r", stdin);
186+
            int d = f[j] - f[j - 1];

187-
        freopen(FNAME ".out", "w", stdout);
187+
            ans += 1ll * c * d * X;

188-
    }
188+
        }

189-
#endif
189+
    }

190-
    ios_base::sync_with_stdio(false);
190+
    cout << ans;

191-
    cin.tie(nullptr);
191+
    //

192-
    int tt = 1;
192+
}

193-
    //    cin >> tt;
193+
signed main() {

194-
    for (int req = 0; req < tt; ++req) {
194+
#ifdef HOME

195-
        unsigned start = clock();
195+
    freopen("input.txt", "r", stdin);

196-
    
196+
    //freopen("input.txt", "w", stdout);

197-
        solve();
197+
#else

198-
    
198+
    if (FNAME != "") {

199-
        unsigned end = clock();
199+
        freopen(FNAME ".in", "r", stdin);

200-
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
200+
        freopen(FNAME ".out", "w", stdout);

201-
        cout << '\n';
201+
    }

202-
        
202+
#endif

203-
    }
203+
    ios_base::sync_with_stdio(false);

204
    cin.tie(nullptr);

205
    int tt = 1;

206
    //    cin >> tt;

207
    for (int req = 0; req < tt; ++req) {

208
        unsigned start = clock();

209
210
        solve();

211
212
        unsigned end = clock();

213
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';

214
        cout << '\n';

215
216
    }

217
}
        

    


            


                                


        

            



                
    

        Public Pastes
    

    
            

    

                    

        

    





    


    
    
    
    
    
    
    
    




    


    



                

            We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.             OK, I Understand
        

    
                

            

                
                    
                
            

            

                Not a member of Pastebin yet?

                Sign Up, it unlocks many cool features!