Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
Code for Q1 > #include> using namespace std; > #define int long long int > #define ll long long int > #define fast \ > ios_base::sync_with_stdio(false); \ > cin.tie(NULL); > #define endl "\n" > > //fast exponentiation > int power(int x, int y, int p = 1000000007) > { > int res = 1; > x = x % p; > if (x == 0) > return 0; > while (y > 0) > { > if (y & 1) > res = (res * x) % p; > y = y >> 1; > x = (x * x) % p; > } > return res % p; > } > > signed main() > { > #ifndef ONLINE_JUDGE > freopen("input.txt", "r", stdin); > freopen("output.txt", "w", stdout); > #endif // ONLINE_JUDGE > fast int tt = 1; > cin >> tt; > for (int loop = 1; loop <= tt; loop++) > { > int n, q, k; > // q operations, and we need to find kth integer after performing swap operation > cin >> n >> q >> k; > unordered_mapmp; > // working on 1 based indexing system > int id[n + 1]; > for (int i = 1; i <= n; i++) > { > id[i] = i; > } > for (int i = 1; i <= q; i++) > { > int left, right; > cin >> left >> right; > mp[left] = right; > } > for (int i = 1; i <= k; i++) > { > if (mp.find(i) == mp.end()){ > // This means the current element is not a part of any swapped range > if(i == k) { > // If it is the Kth element > cout << id[i] << endl; > break; > } > // else it is not the Kth element > continue; > } > // else the current element is part of a swapped range > int leftIndex = i; > int rightIndex = mp[leftIndex]; > int size = rightIndex - leftIndex + 1; // current block has size number of elements > // Number of elements encountered so far are i - 1 > // Total number of elements by including this block = (i - 1) + size > // If the total number of elements by including this exceeds k, then Kth element would be the part of this block > if (i - 1 + size >= k) > { // means the answer is in this range > int newK = k - (i - 1); > int ansIndex = rightIndex - (newK - 1); > cout << id[ansIndex] << endl; > break; > } > else > { // the kth element is not in this range so skip > i = rightIndex; > } > } > } > return 0; > }
Loading Similar Posts
