#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <math.h>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <string.h>
#include <cstring>
#include <queue>
#include <iomanip>
#include <istream>
#include <map>
#include <list>
#include <stack>
#include <numeric>
#include <ostream>
#include <set>
#include <cassert>
#include <sstream>
#include <string>
#include <utility>
#include <stdio.h>
#include <vector>
using namespace std;
#define dout if (debug) cout
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;
#define REP(i,a,n) for (int i=a;i<n;i++)
#define db(x) cerr << #x << " = " << x << endl
#define PER(i,a,n) for (int i=n-1;i>=a;i--)
const int INF = 1000000404;
const ll MOD = 1000000007ll;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
template <typename t1, typename t2> inline void upmax(t1 &a, t2 b) { a = max(a, (t1)b); }
template <typename t1, typename t2> inline void upmin(t1 &a, t2 b) { a = min(a, (t1)b); }
template <typename T>inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T>inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T>inline T sqr(T a) { return a*a; }
template <typename T>inline bool pal(T &x)
{
int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; }return 1;
}
template <typename T>inline void rev(T &x) { int n = SZ(x); REP(i, 0, n / 2) swap(x[i], x[n - i - 1]); }
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
inline ll mp(ll a, ll b) { return (a << 31) + b; }
class compare{
public:
bool operator()(const int a, const int b) const {
return 1;
}
};
int SQ = 400;
#define debug 1
#define N 1111111
int t[N * 4];
int p[N * 4];
int h[N * 4];
void update(int l, int r, int delta, int v = 1, int tl = 1, int tr = 1000000) {
if (l > tr || r < tl) return;
if (l <= tl&&tr <= r) {
t[v] += delta;
return;
}
int tm = (tl + tr) >> 1;
update(l, r, delta, v + v, tl, tm);
update(l, r, delta, v + v + 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = 1000000) {
if (tl == tr) return t[v];
int tm = (tl + tr) >> 1;
if (pos <= tm) return t[v] + get(pos, v + v, tl, tm);
else return t[v] + get(pos, v + v + 1, tm + 1, tr);
}
void solve()
{
int n, m;
cin >> n >> m;
REP(i, 1, n + 1) cin >> h[i];
REP(i, 2, n+1) {
int a = h[i - 1];
int b = h[i];
update(min(a, b), max(a, b), 1);
}
REP(i, 0, m) {
int type, pos, val, H;
cin >> type;
if (type == 1) {
cin >> pos >> val;
int a = h[pos - 1];
int b = h[pos];
int c = h[pos + 1];
if (pos != 1) {
update(min(a, b), max(a, b), -1);
update(min(a, val), max(a, val), 1);
}
if (pos != n) {
update(min(c, b), max(c, b), -1);
update(min(c, val), max(c, val), 1);
}
h[pos] = val;
}
else {
cin >> H;
cout << get(H) << endl;
}
}
}
int main()
{
//freopen("game.in", "r", stdin);
//freopen("game.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
};
//getchar();
// getchar();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 2 |
Correct |
3 ms |
54260 KB |
Output is correct |
| 3 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 4 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 5 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 6 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 7 |
Correct |
3 ms |
54260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 2 |
Correct |
3 ms |
54260 KB |
Output is correct |
| 3 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 4 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 5 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 6 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 7 |
Correct |
3 ms |
54260 KB |
Output is correct |
| 8 |
Runtime error |
139 ms |
54260 KB |
Execution timed out (wall clock limit exceeded) |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 2 |
Correct |
3 ms |
54260 KB |
Output is correct |
| 3 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 4 |
Correct |
0 ms |
54260 KB |
Output is correct |
| 5 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 6 |
Correct |
6 ms |
54260 KB |
Output is correct |
| 7 |
Correct |
3 ms |
54260 KB |
Output is correct |
| 8 |
Runtime error |
139 ms |
54260 KB |
Execution timed out (wall clock limit exceeded) |
| 9 |
Halted |
0 ms |
0 KB |
- |
