abc185_b - Smartphone Addiction
13 Dec 2020 — Tags: implementation — URLSimulate the battery through time.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(ll n, ll t, vector<ii> events)
{
ll ct = 0, battery = n;
events.emplace_back(t, t);
for (auto [a, b] : events)
{
battery = max(0LL, battery - (a - ct));
if (battery == 0)
return false;
battery = min(n, battery + b - a);
ct = b;
}
return true;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, m, t;
cin >> n >> m >> t;
vector<ii> events(m);
for (auto &[a, b] : events)
cin >> a >> b;
cout << (solve(n, t, events) ? "Yes" : "No") << endl;
return 0;
}