| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 870185 |
2023-11-07T07:46:33 Z |
vjudge1 |
Deda (COCI17_deda) |
C++17 |
|
75 ms |
11856 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define mk make_pair
const int N = 4e5 + 7;
int Point[N], Segmin[N], Ans, n, m;
pair<char, pair<int, int>> Ar[N];
pair<int, int> Child[N];
vector <int> node;
void SegmentAns(int u, int w, int ul, int ur) {
if (ur - ul <= 1) {
Ans = ul;
return;
}
if (ur - ul <= 1) return;
int mid = (ur + ul) / 2;
if (Segmin[u * 2] <= w) SegmentAns(u * 2, w, ul, mid);
else SegmentAns(u * 2 + 1, w, mid, ur);
}
void Segment(int u, int w, int ul, int ur) {
if (ul >= w) {
node.push_back(u);
return;
}
if (ur - ul <= 1 || w > ur - 1) return;
int mid = (ur + ul) / 2;
Segment(u * 2, w, ul, mid);
Segment(u * 2 + 1, w, mid, ur);
}
void solve1(int x, int p) {
node.clear(), Ans = -1;
Segment(1, p, 1, (n + 1));
for (int i = 0; i < node.size(); i++) {
if (Segmin[node[i]] <= x) {
SegmentAns(node[i], x, Child[node[i]].f, Child[node[i]].s);
break;
}
}
cout << Ans << "\n";
}
void update(int u, int w, int w1) {
if (u < 1) return;
Segmin[u] = min(Segmin[u], w), update(u / 2, w, w1);
}
void solve() {
for (int i = 1; i <= m; i++) {
if (Ar[i].f == 'M') update(Point[Ar[i].s.s], Ar[i].s.f, Ar[i].s.s);
if (Ar[i].f == 'D') solve1(Ar[i].s.f, Ar[i].s.s);
}
}
void build(int u, int ul, int ur) {
Child[u].f = ul, Child[u].s = ur;
if (ur - ul <= 1) {
Point[ul] = u;
return;
}
int mid = (ur + ul) / 2;
build(u * 2, ul, mid);
build(u * 2 + 1, mid, ur);
}
void input() {
cin >> n >> m;
for (int i = 1; i < N; i++)
Segmin[i] = 1e9 + 7;
for (int i = 1; i <= m; i++)
cin >> Ar[i].f >> Ar[i].s.f >> Ar[i].s.s;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
input(), build(1, 1, (n + 1)), solve();
}
Compilation message
deda.cpp: In function 'void solve1(int, int)':
deda.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < node.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
11856 KB |
Output isn't correct |
| 5 |
Correct |
67 ms |
11500 KB |
Output is correct |
| 6 |
Incorrect |
73 ms |
11604 KB |
Output isn't correct |
| 7 |
Incorrect |
67 ms |
11600 KB |
Output isn't correct |
