Submission #261262

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
2612622020-08-11 15:36:49BertedArcade (NOI20_arcade)C++14
100 / 100
420 ms17876 KiB
#include <iostream>
#include <algorithm>
#include <set>
#include <tuple>
#define pii pair<int, int>
#define fst first
#define snd second
/*
Observe that we can go from a pair to another pair iff:
|Aj - Ai| <= Tj - Ti
Therefore,
Ti - Ai <= Tj - Aj ---> if Ai <= Aj
Ti + Ai <= Tj + Aj ---> if Ai > Aj
Observe that if Ti - Ai <= Tj - Aj for Ai <= Aj
Ti + Ai <= Tj + Aj will also be satisfied.
Therefore, we could sort the array based on Ti - Ai
And change each element in the array into just Ti + Ai
And the problem is now reduced to :
The minimum number of groups required such that each group
is an non-decreasing subsequence of the array.
*/
using namespace std;
set<int> s;
int m, n;
pii ar[500001];
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...