Submission #1087428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087428		Nika533	Global Warming (CEOI18_glo)	C++14	100 / 100	439 ms	29384 KiB

glo

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;

const int N=2e5+5;
int n,m,T,k,x,dp0[N],dp1[N],big=1e18;

struct segmentTree {
     int t[N*4];
     void build(int v, int tl, int tr) {
          if (tl==tr) {
               t[v]=0; return;
          }
          int mid=(tl+tr)/2;
          build(v*2,tl,mid); build(v*2+1,mid+1,tr);
     }
     void update(int v, int tl, int tr, int ind, int val) {
          if (tl==tr) {
               t[v]=max(t[v],val); return;
          }
          int mid=(tl+tr)/2;
          if (ind<=mid) update(v*2,tl,mid,ind,val); 
          else update(v*2+1,mid+1,tr,ind,val);
          t[v]=max(t[v*2],t[v*2+1]);
     }
     int query(int v, int tl, int tr, int l, int r) {
          if (l>r) return 0;
          if (tl==l && tr==r) return t[v];
          int mid=(tl+tr)/2;
          return max(query(v*2,tl,mid,l,min(r,mid)),query(v*2+1,mid+1,tr,max(l,mid+1),r));
     }
} segtree0,segtree1;

void test_case() {
     cin>>n>>x;
     int arr[n+1]; vector<int> v; v.pb(0);
     for (int i=1; i<=n; i++) {
          cin>>arr[i]; v.pb(arr[i]);
     }
     sort(all(v));
     map<int,int> ind;
     for (int i=1; i<=n; i++) {
          if (ind[v[i]]==0) ind[v[i]]=i;
     }
     segtree0.build(1,1,n); segtree1.build(1,1,n);
     for (int i=1; i<=n; i++) {
          int val1=segtree0.query(1,1,n,1,ind[arr[i]]-1);
          int val2=segtree1.query(1,1,n,1,ind[arr[i]]-1);
          int l=1,r=n,idx=0;
          while (l<=r) {
               int mid=(l+r)/2;
               if (v[mid]<arr[i]+x) {
                    idx=mid; l=mid+1;
               }
               else {
                    r=mid-1;
               }
          }
          int val3=segtree0.query(1,1,n,1,idx);
          dp0[i]=val1+1; dp1[i]=max(val2+1,val3+1);
          segtree0.update(1,1,n,ind[arr[i]],dp0[i]);
          segtree1.update(1,1,n,ind[arr[i]],dp1[i]);
     }
     cout<<segtree1.query(1,1,n,1,n)<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message (stderr)

glo.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
glo.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main () {
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25