Submission #49634

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49634	2018-06-01T12:08:46 Z	gs14004	New Home (APIO18_new_home)	C++17	Compilation error	0 ms	0 KB

new_home

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 300005;
 
struct query{
    int pos, t, idx;
    bool operator<(const query &q)const{
        return t < q.t;
    };
}qry[MAXN];
 
struct query2{
    int t, mode, val;
    bool operator<(const query2 &q)const{
        return pi(t, mode) < pi(q.t, q.mode);
    };
};
 
struct rect{ int st, et, y, mode, rpos; };
// mode 1 : [0, y]
// mode -1 : [y, inf]
struct intv{ int s, e, x; };
vector<intv> house[MAXN];
vector<rect> rec;
int n, k, q, ans[MAXN];
const int inf = 500000005;
 
struct rect2{
    int sx, ex, ins;
    bool operator<(const rect2 &r)const{
        return sx < r.sx;
    }
};
 
void process(int h){
    vector<query2> v;
    for(auto &i : house[h]){
        i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
        i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
        if(i.s == i.e) continue;
        v.push_back({i.s, 1, i.x});
        v.push_back({i.e, -1, i.x});
    }
    sort(v.begin(), v.end());
    map<int, int> cnt;
    set<rect2> r;
    r.insert({-1, inf, 0});
    auto insert_rect = [&](int st, int et, int sy, int ey){
        if(st == et) return;
        et--;
        if(sy == -1){
            rec.push_back({st, et, -1, -1, ey});
            return;
        }
        if(ey == inf){
            rec.push_back({st, et, inf, 1, sy});
            return;
        }
        int my = (sy + ey) / 2;
        rec.push_back({st, et, my, 1, sy});
        rec.push_back({st, et, my+1, -1, ey});
    };
    for(int i=0; i<v.size(); i++){
        auto insert_intv = [&](int pos){
            auto l = --r.upper_bound({pos, -1, -1});
            insert_rect(l->ins, v[i].t, l->sx, l->ex);
            rect2 ins1 = {l->sx, pos, v[i].t};
            rect2 ins2 = {pos, l->ex, v[i].t};
            r.erase(l);
            r.insert(ins1);
            r.insert(ins2);
        };
        auto remove_intv = [&](int pos){
            auto nxt = r.lower_bound({pos, -1, -1});
            auto prv = prev(nxt);
            insert_rect(prv->ins, v[i].t, prv->sx, prv->ex);
            insert_rect(nxt->ins, v[i].t, nxt->sx, nxt->ex);
            rect2 ins = {prv->sx, nxt->ex, v[i].t};
            r.erase(prv);
            r.erase(nxt);
            r.insert(ins);
        };
        for(int j=i; j<i+1; j++){
            if(cnt[v[j].val] == 0) insert_intv(v[j].val);
            cnt[v[j].val] += v[j].mode;
            if(cnt[v[j].val] == 0) remove_intv(v[j].val);
        }
    }
}
 
struct query3{
    int pos, l, r, v;
    bool operator<(const query3 &q)const{
        return pos < q.pos;
    }
};
 
vector<query3> mode1,mode2;
// mode1 : disappear after y + 1
// mode2 : appear after y
 
struct seg{
    int seg[1050000], lim;
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
        fill(seg, seg + 1050000, 1e9);
    }
    void add(int l, int r, int val){
        l += lim;
        r += lim;
        while(l < r){
            if(l%2 == 1) seg[l] = min(seg[l], val), l++;
            if(r%2 == 0) seg[r] = min(seg[r], val), r--;
            l >>= 1;
            r >>= 1;
        }
        if(l == r) seg[l] = min(seg[l], val);
    }
    int query(int pos){
        pos += lim;
        int ans = 1e9;
        while(pos){
            ans = min(ans, seg[pos]);
            pos >>= 1;
        }
        return ans;
    }
}seg;
 
int main(){
    scanf("%d %d %d",&n,&k,&q);
    for(int i=0; i<n; i++){
        int x, t, s, e;
        x = rand()%100000000 + 1;
        t = rand()%k +1;
        s = 1;
        e = 100000000;
        scanf("%d %d %d %d",&x,&t,&s,&e);
        house[t].push_back({s, e, x});
    }
    for(int i=1; i<=k; i++){
        house[i].push_back({1, 100000000, 500000000});
    }
    for(int i=0; i<q; i++){
        qry[i].pos = rand()%100000000 + 1;
        qry[i].t = 1;
        scanf("%d %d",&qry[i].pos,&qry[i].t);
        qry[i].idx = i;
    }
    sort(qry, qry + q);
    for(int i=1; i<=k; i++) process(i);
    for(auto &j : rec){
        if(j.mode == 1){
            mode1.push_back({j.y, j.st, j.et, j.rpos});
        }
        else{
            mode2.push_back({j.y, j.st, j.et, j.rpos});
        }
    }
    for(int i=0; i<q; i++) qry[i].t = i;
    sort(qry, qry + q, [&](const query &a, const query &b){
        return a.pos < b.pos;
    });
    sort(mode1.begin(), mode1.end());
    sort(mode2.begin(), mode2.end());
    int ptr = 0;
    seg.init(q + 1);
    for(int i=0; i<q; i++){
        while(ptr < mode2.size() && mode2[ptr].pos <= qry[i].pos){
            seg.add(mode2[ptr].l, mode2[ptr].r, -mode2[ptr].v);
            ptr++;
        }
        int query2 = -seg.query(qry[i].t) - qry[i].pos;
        ans[qry[i].idx] = max(ans[qry[i].idx], query2);
    }
    seg.init(q + 1);
    ptr = mode1.size();
    for(int i=q-1; i>=0; i--){
        while(ptr > 0 && mode1[ptr-1].pos >= qry[i].pos){
            ptr--;
            seg.add(mode1[ptr].l, mode1[ptr].r, mode1[ptr].v);
        }
        int query1 = qry[i].pos - seg.query(qry[i].t);
        ans[qry[i].idx] = max(ans[qry[i].idx], query1);
    }
    for(int i=0; i<q; i++){
        if(ans[i] > 2e8) ans[i] = -1;
        printf("%d\n", ans[i]);
    }
}

Compilation message

new_home.cpp:7:1: error: stray '\302' in program
  
 ^
new_home.cpp:7:2: error: stray '\240' in program
  
  ^
new_home.cpp:9:1: error: stray '\302' in program
     int pos, t, idx;
 ^
new_home.cpp:9:2: error: stray '\240' in program
     int pos, t, idx;
  ^
new_home.cpp:9:3: error: stray '\302' in program
     int pos, t, idx;
   ^
new_home.cpp:9:4: error: stray '\240' in program
     int pos, t, idx;
    ^
new_home.cpp:9:5: error: stray '\302' in program
     int pos, t, idx;
     ^
new_home.cpp:9:6: error: stray '\240' in program
     int pos, t, idx;
      ^
new_home.cpp:9:7: error: stray '\302' in program
     int pos, t, idx;
       ^
new_home.cpp:9:8: error: stray '\240' in program
     int pos, t, idx;
        ^
new_home.cpp:10:1: error: stray '\302' in program
     bool operator<(const query &q)const{
 ^
new_home.cpp:10:2: error: stray '\240' in program
     bool operator<(const query &q)const{
  ^
new_home.cpp:10:3: error: stray '\302' in program
     bool operator<(const query &q)const{
   ^
new_home.cpp:10:4: error: stray '\240' in program
     bool operator<(const query &q)const{
    ^
new_home.cpp:10:5: error: stray '\302' in program
     bool operator<(const query &q)const{
     ^
new_home.cpp:10:6: error: stray '\240' in program
     bool operator<(const query &q)const{
      ^
new_home.cpp:10:7: error: stray '\302' in program
     bool operator<(const query &q)const{
       ^
new_home.cpp:10:8: error: stray '\240' in program
     bool operator<(const query &q)const{
        ^
new_home.cpp:11:1: error: stray '\302' in program
         return t < q.t;
 ^
new_home.cpp:11:2: error: stray '\240' in program
         return t < q.t;
  ^
new_home.cpp:11:3: error: stray '\302' in program
         return t < q.t;
   ^
new_home.cpp:11:4: error: stray '\240' in program
         return t < q.t;
    ^
new_home.cpp:11:5: error: stray '\302' in program
         return t < q.t;
     ^
new_home.cpp:11:6: error: stray '\240' in program
         return t < q.t;
      ^
new_home.cpp:11:7: error: stray '\302' in program
         return t < q.t;
       ^
new_home.cpp:11:8: error: stray '\240' in program
         return t < q.t;
        ^
new_home.cpp:11:9: error: stray '\302' in program
         return t < q.t;
         ^
new_home.cpp:11:10: error: stray '\240' in program
         return t < q.t;
          ^
new_home.cpp:11:11: error: stray '\302' in program
         return t < q.t;
           ^
new_home.cpp:11:12: error: stray '\240' in program
         return t < q.t;
            ^
new_home.cpp:11:13: error: stray '\302' in program
         return t < q.t;
             ^
new_home.cpp:11:14: error: stray '\240' in program
         return t < q.t;
              ^
new_home.cpp:11:15: error: stray '\302' in program
         return t < q.t;
               ^
new_home.cpp:11:16: error: stray '\240' in program
         return t < q.t;
                ^
new_home.cpp:12:1: error: stray '\302' in program
     };
 ^
new_home.cpp:12:2: error: stray '\240' in program
     };
  ^
new_home.cpp:12:3: error: stray '\302' in program
     };
   ^
new_home.cpp:12:4: error: stray '\240' in program
     };
    ^
new_home.cpp:12:5: error: stray '\302' in program
     };
     ^
new_home.cpp:12:6: error: stray '\240' in program
     };
      ^
new_home.cpp:12:7: error: stray '\302' in program
     };
       ^
new_home.cpp:12:8: error: stray '\240' in program
     };
        ^
new_home.cpp:14:1: error: stray '\302' in program
  
 ^
new_home.cpp:14:2: error: stray '\240' in program
  
  ^
new_home.cpp:16:1: error: stray '\302' in program
     int t, mode, val;
 ^
new_home.cpp:16:2: error: stray '\240' in program
     int t, mode, val;
  ^
new_home.cpp:16:3: error: stray '\302' in program
     int t, mode, val;
   ^
new_home.cpp:16:4: error: stray '\240' in program
     int t, mode, val;
    ^
new_home.cpp:16:5: error: stray '\302' in program
     int t, mode, val;
     ^
new_home.cpp:16:6: error: stray '\240' in program
     int t, mode, val;
      ^
new_home.cpp:16:7: error: stray '\302' in program
     int t, mode, val;
       ^
new_home.cpp:16:8: error: stray '\240' in program
     int t, mode, val;
        ^
new_home.cpp:17:1: error: stray '\302' in program
     bool operator<(const query2 &q)const{
 ^
new_home.cpp:17:2: error: stray '\240' in program
     bool operator<(const query2 &q)const{
  ^
new_home.cpp:17:3: error: stray '\302' in program
     bool operator<(const query2 &q)const{
   ^
new_home.cpp:17:4: error: stray '\240' in program
     bool operator<(const query2 &q)const{
    ^
new_home.cpp:17:5: error: stray '\302' in program
     bool operator<(const query2 &q)const{
     ^
new_home.cpp:17:6: error: stray '\240' in program
     bool operator<(const query2 &q)const{
      ^
new_home.cpp:17:7: error: stray '\302' in program
     bool operator<(const query2 &q)const{
       ^
new_home.cpp:17:8: error: stray '\240' in program
     bool operator<(const query2 &q)const{
        ^
new_home.cpp:18:1: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
 ^
new_home.cpp:18:2: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
  ^
new_home.cpp:18:3: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
   ^
new_home.cpp:18:4: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
    ^
new_home.cpp:18:5: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
     ^
new_home.cpp:18:6: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
      ^
new_home.cpp:18:7: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
       ^
new_home.cpp:18:8: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
        ^
new_home.cpp:18:9: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
         ^
new_home.cpp:18:10: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
          ^
new_home.cpp:18:11: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
           ^
new_home.cpp:18:12: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
            ^
new_home.cpp:18:13: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
             ^
new_home.cpp:18:14: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
              ^
new_home.cpp:18:15: error: stray '\302' in program
         return pi(t, mode) < pi(q.t, q.mode);
               ^
new_home.cpp:18:16: error: stray '\240' in program
         return pi(t, mode) < pi(q.t, q.mode);
                ^
new_home.cpp:19:1: error: stray '\302' in program
     };
 ^
new_home.cpp:19:2: error: stray '\240' in program
     };
  ^
new_home.cpp:19:3: error: stray '\302' in program
     };
   ^
new_home.cpp:19:4: error: stray '\240' in program
     };
    ^
new_home.cpp:19:5: error: stray '\302' in program
     };
     ^
new_home.cpp:19:6: error: stray '\240' in program
     };
      ^
new_home.cpp:19:7: error: stray '\302' in program
     };
       ^
new_home.cpp:19:8: error: stray '\240' in program
     };
        ^
new_home.cpp:21:1: error: stray '\302' in program
  
 ^
new_home.cpp:21:2: error: stray '\240' in program
  
  ^
new_home.cpp:30:1: error: stray '\302' in program
  
 ^
new_home.cpp:30:2: error: stray '\240' in program
  
  ^
new_home.cpp:32:1: error: stray '\302' in program
     int sx, ex, ins;
 ^
new_home.cpp:32:2: error: stray '\240' in program
     int sx, ex, ins;
  ^
new_home.cpp:32:3: error: stray '\302' in program
     int sx, ex, ins;
   ^
new_home.cpp:32:4: error: stray '\240' in program
     int sx, ex, ins;
    ^
new_home.cpp:32:5: error: stray '\302' in program
     int sx, ex, ins;
     ^
new_home.cpp:32:6: error: stray '\240' in program
     int sx, ex, ins;
      ^
new_home.cpp:32:7: error: stray '\302' in program
     int sx, ex, ins;
       ^
new_home.cpp:32:8: error: stray '\240' in program
     int sx, ex, ins;
        ^
new_home.cpp:33:1: error: stray '\302' in program
     bool operator<(const rect2 &r)const{
 ^
new_home.cpp:33:2: error: stray '\240' in program
     bool operator<(const rect2 &r)const{
  ^
new_home.cpp:33:3: error: stray '\302' in program
     bool operator<(const rect2 &r)const{
   ^
new_home.cpp:33:4: error: stray '\240' in program
     bool operator<(const rect2 &r)const{
    ^
new_home.cpp:33:5: error: stray '\302' in program
     bool operator<(const rect2 &r)const{
     ^
new_home.cpp:33:6: error: stray '\240' in program
     bool operator<(const rect2 &r)const{
      ^
new_home.cpp:33:7: error: stray '\302' in program
     bool operator<(const rect2 &r)const{
       ^
new_home.cpp:33:8: error: stray '\240' in program
     bool operator<(const rect2 &r)const{
        ^
new_home.cpp:34:1: error: stray '\302' in program
         return sx < r.sx;
 ^
new_home.cpp:34:2: error: stray '\240' in program
         return sx < r.sx;
  ^
new_home.cpp:34:3: error: stray '\302' in program
         return sx < r.sx;
   ^
new_home.cpp:34:4: error: stray '\240' in program
         return sx < r.sx;
    ^
new_home.cpp:34:5: error: stray '\302' in program
         return sx < r.sx;
     ^
new_home.cpp:34:6: error: stray '\240' in program
         return sx < r.sx;
      ^
new_home.cpp:34:7: error: stray '\302' in program
         return sx < r.sx;
       ^
new_home.cpp:34:8: error: stray '\240' in program
         return sx < r.sx;
        ^
new_home.cpp:34:9: error: stray '\302' in program
         return sx < r.sx;
         ^
new_home.cpp:34:10: error: stray '\240' in program
         return sx < r.sx;
          ^
new_home.cpp:34:11: error: stray '\302' in program
         return sx < r.sx;
           ^
new_home.cpp:34:12: error: stray '\240' in program
         return sx < r.sx;
            ^
new_home.cpp:34:13: error: stray '\302' in program
         return sx < r.sx;
             ^
new_home.cpp:34:14: error: stray '\240' in program
         return sx < r.sx;
              ^
new_home.cpp:34:15: error: stray '\302' in program
         return sx < r.sx;
               ^
new_home.cpp:34:16: error: stray '\240' in program
         return sx < r.sx;
                ^
new_home.cpp:35:1: error: stray '\302' in program
     }
 ^
new_home.cpp:35:2: error: stray '\240' in program
     }
  ^
new_home.cpp:35:3: error: stray '\302' in program
     }
   ^
new_home.cpp:35:4: error: stray '\240' in program
     }
    ^
new_home.cpp:35:5: error: stray '\302' in program
     }
     ^
new_home.cpp:35:6: error: stray '\240' in program
     }
      ^
new_home.cpp:35:7: error: stray '\302' in program
     }
       ^
new_home.cpp:35:8: error: stray '\240' in program
     }
        ^
new_home.cpp:37:1: error: stray '\302' in program
  
 ^
new_home.cpp:37:2: error: stray '\240' in program
  
  ^
new_home.cpp:39:1: error: stray '\302' in program
     vector<query2> v;
 ^
new_home.cpp:39:2: error: stray '\240' in program
     vector<query2> v;
  ^
new_home.cpp:39:3: error: stray '\302' in program
     vector<query2> v;
   ^
new_home.cpp:39:4: error: stray '\240' in program
     vector<query2> v;
    ^
new_home.cpp:39:5: error: stray '\302' in program
     vector<query2> v;
     ^
new_home.cpp:39:6: error: stray '\240' in program
     vector<query2> v;
      ^
new_home.cpp:39:7: error: stray '\302' in program
     vector<query2> v;
       ^
new_home.cpp:39:8: error: stray '\240' in program
     vector<query2> v;
        ^
new_home.cpp:40:1: error: stray '\302' in program
     for(auto &i : house[h]){
 ^
new_home.cpp:40:2: error: stray '\240' in program
     for(auto &i : house[h]){
  ^
new_home.cpp:40:3: error: stray '\302' in program
     for(auto &i : house[h]){
   ^
new_home.cpp:40:4: error: stray '\240' in program
     for(auto &i : house[h]){
    ^
new_home.cpp:40:5: error: stray '\302' in program
     for(auto &i : house[h]){
     ^
new_home.cpp:40:6: error: stray '\240' in program
     for(auto &i : house[h]){
      ^
new_home.cpp:40:7: error: stray '\302' in program
     for(auto &i : house[h]){
       ^
new_home.cpp:40:8: error: stray '\240' in program
     for(auto &i : house[h]){
        ^
new_home.cpp:41:1: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
 ^
new_home.cpp:41:2: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
  ^
new_home.cpp:41:3: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
   ^
new_home.cpp:41:4: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
    ^
new_home.cpp:41:5: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
     ^
new_home.cpp:41:6: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
      ^
new_home.cpp:41:7: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
       ^
new_home.cpp:41:8: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
        ^
new_home.cpp:41:9: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
         ^
new_home.cpp:41:10: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
          ^
new_home.cpp:41:11: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
           ^
new_home.cpp:41:12: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
            ^
new_home.cpp:41:13: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
             ^
new_home.cpp:41:14: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
              ^
new_home.cpp:41:15: error: stray '\302' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
               ^
new_home.cpp:41:16: error: stray '\240' in program
         i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
                ^
new_home.cpp:42:1: error: stray '\302' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
 ^
new_home.cpp:42:2: error: stray '\240' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
  ^
new_home.cpp:42:3: error: stray '\302' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
   ^
new_home.cpp:42:4: error: stray '\240' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
    ^
new_home.cpp:42:5: error: stray '\302' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
     ^
new_home.cpp:42:6: error: stray '\240' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
      ^
new_home.cpp:42:7: error: stray '\302' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
       ^
new_home.cpp:42:8: error: stray '\240' in program
         i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
        ^
new_home.cpp:42:9: error: stray '\302' in program
         i.e = upper_bound(qry,