Submission #259412

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
259412	2020-08-07 18:30:01	ChrisT	Divide and conquer (IZhO14_divide)	C++17	100 / 100	78 ms	8808 KiB

divide

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 2e5 + 5, LOG = 18, MOD = 1e9 + 7;
ll bit[MN];
vector<ll> xs;
int getx (ll x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
ll x[MN], g[MN], e[MN];
void update (int i, ll v) {
  for (i=MN-i;i<MN;i+=i&-i)
    bit[i] = min(bit[i],v);
}
ll query (int i) {
  ll ret = 1e18;
  for (i=MN-i;i;i^=i&-i)
    ret = min(ret,bit[i]);
  return ret;
}
int main () {
  int n;
  scanf ("%d",&n);
  for (int i = 1; i <= n; i++) {
    scanf ("%lld %lld %lld",&x[i],&g[i],&e[i]);
    g[i] += g[i-1]; e[i] += e[i-1];
    xs.push_back(x[i]-e[i]); xs.push_back(x[i]-e[i-1]);
  }
  sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
  memset(bit,0x3f,sizeof bit); ll ret = -1e18;
  for (int i = 1; i <= n; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&n);
  ~~~~~~^~~~~~~~~
divide.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld %lld",&x[i],&g[i],&e[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52