#include <bits/stdc++.h>
using namespace std;
/* higher types */
typedef long long ll;
typedef long double ld;
/* pairs */
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef pair<ld, ld> pld;
/* vectors */
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
typedef vector<pld> vpld;
/* 2d vectors */
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
typedef vector<vs> vvs;
typedef vector<vb> vvb;
/* initialisation */
#define initvvi(mat, n, x) for(auto u : mat) u = vi(n, x);
#define initvvl(mat, n, x) for(auto u : mat) u = vl(n, x);
#define initvvb(mat, n, x) for(auto u : mat) u = vb(n, x);
#define initvvd(mat, n, x) for(auto u : mat) u = vd(n, x);
#define initvvs(mat, n, x) for(auto u : mat) u = vs(n, x);
/* loops */
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define each(u, v) for(auto u : v )
/* input */
#define rv(v) for(auto &u : v) cin >> u;
#define rm(mat, m) for(ll j = 0; j <= (ll)(m-1)) for(auto u : mat[j]) cin >> u;
/* output */
#define pv(v) for(auto x : v) cout << x << ' '; cout << nl;
#define pm(m) for(auto n : m) pv(n);
/* shortforms */
#define fr first
#define sc second
#define pb push_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
/* constants */
const ll infl = numeric_limits<long long int>::max();
const int infi = numeric_limits<int>::max();
const int modi = 1e9 + 7;
const ll modl = 1e9 + 7;
ll n, m;
vl y;
vl seg;
void add(ll increment, ll node)
{
node += 2000000;
seg[node] += increment;
for(node /= 2; node >= 1; node /= 2)
seg[node] = seg[2*node] + seg[2*node+1];
}
ll sum(ll a, ll b)
{
a += 2000000;
b += 2000000;
ll s = 0;
while(a <= b)
{
if(a%2 == 1) s+= seg[a++];
if(b%2 == 0) s+= seg[b++];
a /= 2;
b /= 2;
}
return s;
}
void remove_line(ll a, ll b)
{
if(a > b)
swap(a, b);
add(-1, a + 1);
add(1, b);
}
void add_line(ll a, ll b)
{
if(a > b)
swap(a, b);
add(1, a + 1);
add(-1, b);
}
void solve()
{
cin >> n >> m;
y.resize(n + 1);
seg.resize(4000000 + 2, 0);
cin >> y[1];
fur(i, 2, n)
{
cin >> y[i];
add_line(y[i], y[i-1]);
}
while(m--)
{
int type;
cin >> type;
if(type == 2)
{
ll h;
cin >> h;
cout << sum(1, h) << nl;
continue;
}
ll i, h;
cin >> i >> h;
if(i != 1)
{
remove_line(y[i], y[i-1]);
add_line(h, y[i-1]);
}
if(i != n)
{
remove_line(y[i], y[i+1]);
add_line(h, y[i+1]);
}
y[i] = h;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t = 1;
/* cin >> t; */
while(t--)
{
solve();
}
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
game.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
