oj.uz

Submission #941273

# Submission time Handle Problem Language Result Execution time Memory
941273 2024-03-08T12:21:39 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 132 ms 13504 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 3e5 + 5;
const int INF = 1e18;
int n, m;

struct seg{
    int l, r, id;
    seg(){}
    seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
        if(r < l) r += n;
    }
    bool operator < (const seg& other) const{
        if(l != other.l) return l < other.l;
        return r < other.r;
    }
};

class comp{
    public:
        bool operator ()(seg a, seg b){
            if(a.r != b.r) return a.r > b.r;
            else return a.l > b.l;
        }
};

int st[maxn * 4], tag[maxn * 4];

void cast(int val, int v){
    st[v] += val, tag[v] += val;
}

void push(int v){
    if(tag[v]){
        cast(tag[v], v * 2);
        cast(tag[v], v * 2 + 1);
        tag[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        st[v] += val, tag[v] += val;
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
    st[v] = min(st[v * 2], st[v * 2 + 1]);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return INF;
    if(l <= L && r >= R) return st[v];
    push(v);
    int m = (L + R) / 2;
    return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
void insert(int l, int r, int val){
    r %= n;
    if(l <= r) upd(l, r, val);
    else upd(l, n - 1, val), upd(0, r, val);
}

bool ck(seg a){
    a.r %= n;
    if(a.l <= a.r) return qry(a.l, a.r) >= 2;
    else return min(qry(a.l, n - 1), qry(0, a.r)) >= 2;
}
signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        insert(a, b, 1);
        e.pb(seg(a, b, i));
    }
    if(qry(0, n - 1) < 2){
        cout<<"impossible\n";
        return 0;
    }
    sort(e.begin(), e.end());
    int st = e[0].l, r = e[0].l - 1;
    vector<int> ans(m);
    int id = 0;
    priority_queue<seg, vector<seg>, comp> q;
    int dist = 0;
    while(true){
        // cout<<"r : "<<r<<"\n";
        while(id < m && e[id].l <= r + 1){
            // cout<<"push : "<<e[id].l<<" "<<e[id].r<<" "<<e[id].id<<"\n";
            q.push(e[id]);
            id++;
        }
        while(true){
            if(q.empty()){
                cout<<"impossible\n";
                return 0;
            }
            seg cur = q.top(); q.pop();
            if(!ck(cur)) continue;
            if(cur.r <= r) continue;
            // cout<<"use : "<<cur.l<<" "<<cur.r<<" "<<cur.id<<"\n";
            insert(cur.l, cur.r, -1);
            ans[cur.id] = 1;
            dist += cur.r - r;
            r = cur.r;
            break;
        }
        if(dist >= n) break;
    }
    for(auto x : ans) cout<<x;
    cout<<"\n";
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:95:9: warning: unused variable 'st' [-Wunused-variable]
   95 |     int st = e[0].l, r = e[0].l - 1;
      |         ^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10184 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 22 ms 8916 KB Output is correct
4 Correct 43 ms 11036 KB Output is correct
5 Correct 70 ms 10796 KB Output is correct
6 Correct 38 ms 10696 KB Output is correct
7 Correct 73 ms 10580 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 72 ms 11500 KB Output is correct
11 Correct 56 ms 11460 KB Output is correct
12 Correct 67 ms 11728 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 72 ms 11888 KB Output is correct
16 Correct 22 ms 8388 KB Output is correct
17 Correct 132 ms 13504 KB Output is correct
18 Correct 90 ms 9376 KB Output is correct
19 Correct 5 ms 6936 KB Output is correct
20 Correct 73 ms 8656 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -