AtCoder Beginner Contest 217

##[A - Lexicographic Order](https://atcoder.jp/contests/abc217/tasks/abc217_a)

O(1)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    string a, b;
    cin >> a >> b;
 
    if(a < b) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}
```

##[B - AtCoder Quiz](https://atcoder.jp/contests/abc217/tasks/abc217_b)

O(1)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
 
    string str[4] = {"ABC" , "ARC" , "AGC" , "AHC"};
 
    if(s1 != "ABC" && s2 != "ABC" && s3 != "ABC"){
        cout << "ABC" << endl;
    }
    if(s1 != "ARC" && s2 != "ARC" && s3 != "ARC"){
        cout << "ARC" << endl;
    }
    if(s1 != "AGC" && s2 != "AGC" && s3 != "AGC"){
        cout << "AGC" << endl;
    }
    if(s1 != "AHC" && s2 != "AHC" && s3 != "AHC"){
        cout << "AHC" << endl;
    }
 
    return 0;
}
```

##[C - Inverse of Permutation](https://atcoder.jp/contests/abc217/tasks/abc217_c)

O(N)
問題文の文章が難しいですね。
問題文は、iの数列とQ_iの数列の間に、P_iの数列を中継として用意するイメージです。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int N;
    cin >> N;
 
    vector<int> P(N);
    rep(i, N){
        int p;
        cin >> p;
        P[i] = p-1;
    }
 
    vector<int> Q(N);
    rep(i, N) Q[P[i]] = i;
 
    rep(i, N){
        cout << Q[i] + 1;
        if(i+1<N) cout << " ";
        else cout << endl;
    }
 
    return 0;
}
```

##[D - Cutting Woods](https://atcoder.jp/contests/abc217/tasks/abc217_d)

O(logN)
全探索だと間に合わないです。
x_iをデータ構造で昇順に保持し、二分探索で検索する問題です。
ここまでは分かったのですが、setを使用する事、st.lower_bound(x)のような記載方法を知りませんでした。
ループ内でデータ構造のコピーを作成、それを連続で行いTLEになりました。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int L, Q;
    cin >> L >> Q;
 
    set<int> st;
    st.insert(0);
    st.insert(L);
 
    rep(i, Q){
        int c, x;
        cin >> c >> x;
 
        if(c==1){
            st.insert(x);
        }else{
            auto it = st.lower_bound(x);
            cout << *it - *prev(it) << endl;
        }
    }

    return 0;
}
```