Submission #850917

#	Time	Username	Problem	Language	Result	Execution time	Memory
850917		Dextar	Radio Towers (IOI22_towers)	C++17	29 / 100	4018 ms	26912 KiB

towers

#include <cstdio>
#ifdef DEBUG
    #define D(X) X
#else
    #define D(X)
#endif
#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
#define pi 3.14159265359
#define pub push_back
#define pob pop_back
#define pari pair<int,int>
#define parli pair<long, long>

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ll INF2 = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

bool comp(pari& v1, pari& v2)
{
    return v1.fr < v2.fr;
}


struct seg {
      vector<int> tree;
      int sz;

      void build(int n) {
          sz = 1;
          while(sz<n) {
              sz *= 2;
          }
          tree.resize(2*sz + 1, 0);
      }

      void clean()
      {
          for(int i=0; i<tree.size(); i++) {
              tree[i] = 0;
          }
      }

      void recSet(int idx, int lx, int rx, int i, int val) {
           if(rx-lx==1) {
               tree[idx] = val;
               return;
           }
           int mid = (lx+rx)/2;
           if(i<mid) {
               recSet(2*idx+1, lx, mid, i, val);
           } else
           {
               recSet(2*idx+2, mid, rx, i, val);
           }
           tree[idx] = max(tree[2*idx+1], tree[2*idx+2]);
      }

      void setX(int i, int val) {
          recSet(0, 0, sz, i, val);
      }

      int rec_range(int idx, int lx, int rx, int l, int r) {
          if(lx>=l&&rx<=r) {
              return tree[idx];
          }
          if(rx<=l||lx>=r) return 0;
          int mid = (lx+rx)/2;
          int left = rec_range(2*idx+1, lx, mid, l, r);
          int right = rec_range(2*idx+2, mid, rx, l, r);
          return max(left, right);
      }

      int range(int l, int r) {
          if(l>=r) {
             return 0;
          }
          return rec_range(0, 0, sz, l, r);
      }
};

struct seg2 {
      vector<int> tree;
      int sz;

      void build(int n) {
          sz = 1;
          while(sz<n) {
              sz *= 2;
          }
          tree.resize(2*sz + 1, INF);
      }

      void clean()
      {
          for(int i=0; i<tree.size(); i++) {
              tree[i] = INF;
          }
      }

      void recSet(int idx, int lx, int rx, int i, int val) {
           if(rx-lx==1) {
               tree[idx] = val;
               return;
           }
           int mid = (lx+rx)/2;
           if(i<mid) {
               recSet(2*idx+1, lx, mid, i, val);
           } else
           {
               recSet(2*idx+2, mid, rx, i, val);
           }
           tree[idx] = min(tree[2*idx+1], tree[2*idx+2]);
      }

      void setX(int i, int val) {
          recSet(0, 0, sz, i, val);
      }

      int rec_range(int idx, int lx, int rx, int l, int r) {
          if(lx>=l&&rx<=r) {
              return tree[idx];
          }
          if(rx<=l||lx>=r) return INF;
          int mid = (lx+rx)/2;
          int left = rec_range(2*idx+1, lx, mid, l, r);
          int right = rec_range(2*idx+2, mid, rx, l, r);
          return min(left, right);
      }

      int range(int l, int r) {
          return rec_range(0, 0, sz, l, r);
      }

      int low1(int idx, int lx, int rx, int l, int r, int val, int dir)
      {
           if(tree[idx]>=val||l>=rx||lx>=r) {
              if(dir==0)
                return -1;
              return INF;
           }
           if(rx-lx==1) {
               return lx;
           }
           int mid = (lx+rx)/2;
           int id1 = low1(2*idx+1, lx, mid, l, r, val, dir);
           int id2 = low1(2*idx+2, mid, rx, l, r, val, dir);
           if(dir==0) {
               return max(id1, id2);
           }
           return min(id1, id2);
      }

      int low1(int l, int r, int val, int dir)
      {
          return low1(0, 0, sz, l, r, val, dir);
      }
};


vector<int> dp;
seg mint, maxt, st2;
map<int, int> ord;
vector<int> h;
int res = 0;
int center = -1;
vector<int> pref, left1, right1, difh;
int qcnt = 0;
seg2 st1;


void init2(int l, int r, int d)
{
    int n = h.size();
    res = 0;
    for(int i=0; i<=n; i++) {
        dp[i] = 0;
    }
    vector<int> used(n+1, 0);
    vector<int> nums;
    for(int i=l; i<=r; i++) {
        int f1 = 0, f2 = 0;
        nums.pub(h[i]);
        nums.pub(h[i]-d);
        nums.pub(h[i]+d);
        if(i>l) {
            if(h[i]>=h[i-1]) {
                f1 = 1;
            } else
            {
                f1 = 2;
            }
        }
        if(i<r) {
            if(h[i]>=h[i+1]) {
                f2 = 1;
            } else
            {
                f2 = 2;
            }
        }
        if(f1==0) {
            f1 = f2;
        }
        if(f2==0) {
            f2 = f1;
        }
        if(f1==f2) {
            used[i] = f1;
        }
    }
    sort(nums.begin(), nums.end());
    ord.clear();
    ord[nums[0]] = 0;
    int sz = nums.size();
    for(int i=1; i<sz; i++) {
        if(nums[i]>nums[i-1]) {
            ord[nums[i]] = ord[nums[i-1]] + 1;
        } else
        {
            ord[nums[i]] = ord[nums[i-1]];
        }
    }
    mint.clean();
    maxt.clean();
    mint.build(sz);
    maxt.build(sz);

    for(int i=r; i>=l; i--) {
        if(used[i]==0) {
            continue;
        }
        if(used[i]==1&&h[i]-d>0) {
            dp[i] = mint.range(0, ord[h[i]-d] + 1);
            maxt.setX(ord[h[i]], dp[i]);
        }
        if(used[i]==2) {
            dp[i] = 1 + maxt.range(ord[h[i]+d], sz);
            mint.setX(ord[h[i]], dp[i]);
        }
        res = max(res, dp[i]);
    }
}

void calc_pref()
{
    int n = h.size();
    pref.resize(n+1);
    pref[0] = 0;
    for(int i=1; i<=n; i++) {
        pref[i] = pref[i-1];
        if(i>1&&i<n) {
            if(h[i-1]<h[i-2]&&h[i-1]<h[i]) {
                pref[i]++;
            }
        } else if(i>1)
        {
            if(h[i-1]<h[i-2]) {
                pref[i]++;
            }
        } else
        {
            if(h[i-1]<h[i]) {
                pref[i]++;
            }
        }
    }
}

void all_arr()
{
    int n = h.size();
    left1.resize(n, INF);
    right1.resize(n, -1);
    st1.build(n);
    st2.build(n);
    for(int i=0; i<n; i++) {
        st1.setX(i, h[i]);
        st2.setX(i, h[i]);
    }
    difh.resize(n);
    for(int i=0; i<n; i++) {
        pari p = {h[i], i};
        left1[p.sc] = st1.low1(0, p.sc, p.fr, 0);
        right1[p.sc] = st1.low1(p.sc + 1, n, p.fr, 1);
        int h1 = 2*INF+10, h2 = h1;
        if(left1[p.sc]!=-1) {
            h1 = st2.range(left1[p.sc]+1, p.sc);
        }
        if(right1[p.sc]!=INF) {
            h2 = st2.range(p.sc+1, right1[p.sc]);
        }  //cout<<h1<<endl;
        difh[p.sc] = min(h1, h2) - p.fr;
    }
    sort(difh.begin(), difh.end());
}


void init(int n, vector<int> h2)
{
    h.resize(n);
    for(int i=0; i<n; i++) {
        h[i] = h2[i];
    }
    dp.resize(n+1);
    int idx = 1;
    while(idx<n&&h[idx]>=h[idx-1]) {
        idx++;
    }
    center = idx - 1;
    while(idx<n&&h[idx]<=h[idx-1]) {
        idx++;
    }
    calc_pref();
    if(idx==n) {
        return;
    }
    center = -1;
    init2(0, n - 1, 1);
}

int max_towers(int l, int r, int d)
{
    qcnt++;
    int n = h.size();
    if(n==1) {
        return 1;
    }
    if(l==r) {
        return 1;
    }
    if(center!=-1) {
        if(r<=center||l>=center) {
            return 1;
        }
        if(h[center]-h[l]>=d&&h[center]-h[r]>=d) {
            return 2;
        }
        return 1;
    }
    if(d==1) {
        if(qcnt==1) {
            calc_pref();
        }
        int ans = pref[r] - pref[l+1];
        if(h[l]<h[l+1]) {
            ans++;
        }
        if(h[r]<h[r-1]) {
            ans++;
        }
        return ans;
    }
    /*
    for(int i=0; i<n; i++) {
        //cout<<left1[i]<<" ";
        //cout<<right1[i]<<" ";
        //cout<<difh[i]<<" ";
    }
    //cout<<endl;
    */
    if(l==0&&r==h.size()-1) {
        if(qcnt==1) {
            all_arr();
        }
        int lo = 0, hi = n - 1;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(difh[mid]>=d) {
                hi = mid - 1;
            } else
            {
                lo = mid + 1;
            }
        }
        return n - lo;
    }
    if(qcnt==1) {
        qcnt = 7;
        init2(l, r, d);
        return res;
    }
    return res;
}

/*
7
10 20 60 40 50 30 70
*/

/*
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //D(freopen("input.txt","r",stdin);)
    //D(freopen("ouput.txt","w",stdout);)
    int t = 1;
    //cin >> t;
    loop:
    while(t--)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i=0; i<n; i++) {
            cin >> a[i];
        }
        init(n, a);
        int res = max_towers(0, 6, 10);
        if(res==0) {
            res = 1;
        }
        cout << res;
    }
    return 0;
}
*/

Compilation message (stderr)

towers.cpp: In member function 'void seg::clean()':
towers.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |           for(int i=0; i<tree.size(); i++) {
      |                        ~^~~~~~~~~~~~
towers.cpp: In member function 'void seg2::clean()':
towers.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |           for(int i=0; i<tree.size(); i++) {
      |                        ~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:366:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  366 |     if(l==0&&r==h.size()-1) {
      |              ~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23