Pranky's blog

By Pranky, history, 8 years ago, In English

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. :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it
    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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