Блог пользователя Pranky

Автор Pranky, история, 8 лет назад, По-английски

Hi, Tried solving MKTHNUM — K-th Number Using MO's algorithm. I am getting a WA but I am having a hard time finding a mistake in my code. My code passes a sample test which is offered on the problem site and I tested it using spojtoolkit and things there were looking good.

I would be really happy if a more experienced coder helped me. I think it could be beneficial to the community since I couldn't find an approach using MO's algorithm online to this problem.

Here is my code:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
 
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
#define pc putchar_unlocked
#define pb push_back
#define gdc __gdc
#define endl '\n'
#define Y second
#define X first
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const pii dir_t1[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const pii dir_t2[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, 1}};
 
const ll LLINF = numeric_limits<ll>::max() / 2;
const int INF = 1e9 + 11;
const int MOD = 1e9 + 7;
const int ASCII = 300;
 
const int MAX_N = 1e5 + 11;
const int MAX_M = 5e3 + 11;
const int BLOCK = ceil(sqrt(MAX_N));
const int MAX_L = ceil(log2(MAX_N));
 
struct Query {
    ll lo, hi, id, k;
    inline bool operator < (Query &other) const {
        if (lo / BLOCK != other.lo / BLOCK)
            return lo / BLOCK < other.lo / BLOCK;
        return hi < other.hi;
    }
} q[MAX_M];
 
ll n, m;
ll arr[MAX_N];
ll ans[MAX_M];
ordered_set<ll> dp;
 
template <typename T> T input() {
    T res;
    cin >> res;
    return res;
}
 
// FAST I/O
inline void scan_int(ll &x) {
    register int c = gc();
    int neg = 0;
 
    while ((c < '0' || c > '9') && c != '-')
        c = gc();
 
    if (c == '-')
        neg = 1, c = gc();
 
    for (x = 0; c >= '0'  && c <= '9'; c = gc())
        x = (x << 1 ) + ( x << 3) + c - 48;
 
    if (neg)
        x *= -1;
}
 
inline void print_int(ll x) {
    ll rev, exp_10 = 0;
    if (x == 0) {
        pc('0'), pc('\n');
        return;
    }
 
    for (rev = x; rev % 10 == 0; rev /= 10)
        ++exp_10;
 
    for (rev = 0; x; x /= 10)
        rev = (rev << 3) + (rev << 1) + x % 10;
 
    while (rev)
        pc(rev % 10 + '0'), rev /= 10;
    while (exp_10--)
        pc('0');
    pc('\n');
}
 
int main() {
 
    scan_int(n), scan_int(m);
    for (int i = 0; i < n; ++i)
        scan_int(arr[i]);
    for (int i = 0; i < m; ++i) {
        scan_int(q[i].lo), scan_int(q[i].hi), scan_int(q[i].k);
        --q[i].lo, --q[i].hi, --q[i].k, q[i].id = i;
    }
 
    sort(q, q + m);
    int l = 0, r = 0;
    for(int i = 0;  i < m; ++i) {
		while(l < q[i].lo)
            dp.erase(arr[l++]);
		while(l > q[i].lo)
            dp.insert(arr[--l]);
 
		while(r <= q[i].hi) {
            if (l <= r)
                dp.insert(arr[r]);
            ++r;
        }
		while(r > q[i].hi + 1)
            dp.erase(arr[--r]);
 
        ans[q[i].id] = *dp.find_by_order(q[i].k);
	}
 
    for (int i = 0; i < m; ++i)
        print_int(ans[i]);
 
    return 0;
}

Thank you for any help in advance. :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Pranky (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

I think you move r incorrectly.

...
while(r < q[i].hi) dp.insert(arr[++r]);
while(r > q[i].hi) dp.erase(arr[r--]);
...
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

I see that in your printing function you ignore negative numbers, so on test

1 1
-100
1 1 1

your program will say 100, but it's not a correct answer. Btw, I think that your implementation of Mo's algorithm is OK.

PS: I'm not sure that Mo's algorithm with your ordered set will pass time limit.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
    for(int i = 0;  i < m; ++i) {
		while(l < q[i].lo)
            dp.erase(arr[l++]);
		while(l > q[i].lo)
            dp.insert(arr[--l]);
 
		while(r <= q[i].hi) {
            if (l <= r)
                dp.insert(arr[r]);
            ++r;
        }
		while(r > q[i].hi + 1)
            dp.erase(arr[--r]);
 
        ans[q[i].id] = *dp.find_by_order(q[i].k);
	}

I guess the order of statements is wrong here. Let us assume current l, r = (2, 3) and new l, r = (10, 20). In first while loop, you delete elements from 2..9. Which means deleting elements that do not exist in set yet. In third while loop, you add elements from 4..29. So the set contains wrong elements. When using MO, I always put insert's first and then remove's.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem with the erase function is that it erases all occurrences of the number in the set. This would be problematic for test cases like

3 2

2 2 3

1 2 1

2 3 1

The correct output is

2

2

but your code outputs

2

3