Submission #870184

#TimeUsernameProblemLanguageResultExecution timeMemory
870184vjudge1Deda (COCI17_deda)C++17
60 / 140
28 ms5716 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define mk make_pair const int N = 1e5 + 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 (stderr)

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 timeMemoryGrader output
Fetching results...