#779832 (C++14) No.1996 <><

提出ソース

結果

問題	No.1996 <><
ユーザー	Endered
提出日時	2022-07-20 20:08:27
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	147 ms / 2,000 ms
コード長	7,237 bytes
コンパイル時間	1,882 ms
コンパイル使用メモリ	182,888 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-02 14:07:48
合計ジャッジ時間	4,142 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	72 ms 5,376 KB
testcase_12	AC	147 ms 5,376 KB
testcase_13	AC	126 ms 5,376 KB
testcase_14	AC	120 ms 5,376 KB
testcase_15	AC	96 ms 5,376 KB
testcase_16	AC	87 ms 5,376 KB
testcase_17	AC	102 ms 5,376 KB
testcase_18	AC	55 ms 5,376 KB
testcase_19	AC	65 ms 5,376 KB
testcase_20	AC	72 ms 5,376 KB
testcase_21	AC	92 ms 5,376 KB
testcase_22	AC	107 ms 5,376 KB
testcase_23	AC	5 ms 5,376 KB
testcase_24	AC	59 ms 5,376 KB
testcase_25	AC	30 ms 5,376 KB
testcase_26	AC	50 ms 5,376 KB
testcase_27	AC	11 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	26 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	10 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE
#define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
    ll modpow(ll x, ll b,ll mod=MOD){
        ll res = 1;
        while(b){
            if(b&1)res = res * x % mod;
            x = x * x % mod;
            b>>=1;
        }
        return res;
    }

    ll modinv(ll x){
        return modpow(x, MOD-2);
    }

    bool was_output = false;

    void print();
    template <class t> void print(const vector<t> &);
    template <class t, class u> void print(const pair<t, u> &);
    template <class t> void print(const t&);
    template <class Head, class... Tail> void print(const Head&, const Tail&...);

    template <class t> void println(const vector<vector<t>>&);
    template <class t> void println(const vector<t>&);
    template <class t> void println(const t&);
    template <class Head, class... Tail> void println(const Head&, const Tail&...);
    void println();
    void newline();

    void print(){
        return;
    }

    template <class t>
    void print(const vector<t>&x){
        for(const t&i:x)print(i);
    }
    template <class t, class u>
    void print(const pair<t,u>&p){
        print(p.first);
        print(p.second);
    }
    template <class t>
    void print(const t&x){
        if(was_output)cout<<" ";
        cout<<x;
        was_output = true;
    }
    template <class Head, class... Tail>
    void print(const Head&head,const Tail&...tail){
        print(head);
        print(tail...);
    }

    template<class t>
    void println(const vector<vector<t>>&x){
        for(vector<t> i:x)println(i);
    }
    template<class t>
    void println(const vector<t>&x){
        for(const t&i:x)print(i);
        println();
    }
    template <class t>
    void println(const t&x){
        print(x);
        println();
    }
    void println(){
        if(was_output){
            cout << endl;
            was_output = false;
        }
    }
    template <class Head, class... Tail>
    void println(const Head&head,const Tail&...tail){
        print(head);
        println(tail...);
    }

    void newline(){
        was_output = true;
        println();
    }

    template<class t>
    istream& operator>>(istream&is, vector<t>&x){
        for(auto &i:x)is >> i;
        return is;
    }

    template<class t, class u>
    istream& operator>>(istream&is, pair<t, u>&x){
        is >> x.first >> x.second;
        return is;
    }

    template<class t>
    ostream& operator<<(ostream&os, vector<t> &v){
        os << "{";
        for(t &i:v){
            os << i << ", ";
        }
        os << "}";
        return os;
    }

    template<class t = long long>
    t in(){
        t res; cin >> res; return res;
    }

    template<class t>
    vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
        sort(line.begin(),line.end(),comp);
        return line;
    }

    template<class t>
    vector<t> reversed(vector<t> line){
        reverse(line.begin(),line.end());
        return line;
    }
    string reversed(string str){
        reverse(str.begin(),str.end());
        return str;
    }

    long long gcd(long long a,long long b){
        while(b){
            a %= b;
            swap(a,b);
        }
        return a;
    }

    long long lcm(long long a,long long b){
        return a / gcd(a,b) * b;
    }

    class output_initializer{
    public:
        output_initializer(){
            ios::sync_with_stdio(false);
            cin.tie(nullptr);
            cout << setprecision(20);
        }
    };output_initializer OUTPUT_INITIALIZER_INSTANCE = output_initializer();
}

using namespace templates;


template<long long mod>
class modint{
	public:
		long long x;
		modint(long long a){x=a%mod;if(x<0)x+=mod;}
		modint(){x=0;}

		modint pow(long long a){
			modint res(1), b(x);
			while(a){
				if(a&1)res*=b;
				b*=b;
				a>>=1;
			}
			return res;
		}

		modint inv(){return pow(mod-2);}

		modint& operator+=(modint a){x=(x+a.x)%mod;return *this;}
		modint& operator-=(modint a){x=x-a.x;if(x<0)x+=mod;return *this;}
		modint& operator*=(modint a){x=x*a.x%mod;return *this;}
		modint& operator/=(modint a){x=x*a.inv().x%mod;return *this;}

		modint operator+(modint a){return modint(x)+=a;}
		modint operator-(modint a){return modint(x)-=a;}
		modint operator*(modint a){return modint(x)*=a;}
		modint operator/(modint a){return modint(x)/=a;}

		modint operator-(){return modint(x);}

		bool operator==(const modint a){return x == a.x;}
		bool operator<(const modint a){return x < a.x;}
		bool operator>(const modint a){return x > a.x;}
};

template<long long mod>
ostream& operator<<(ostream& os, const modint<mod>& a){
	os << a.x;
	return os;
}

using mint = modint<MOD>;


template<class T>
class binary_indexed_tree{
public:
    int n;
    vector<T> data;
    T init;
    binary_indexed_tree(int n,T init=T(0)):n(n+1),data(n+1,init),init(init){}

    void add(int p,T v){
        for(int i=p+1;i<=n;i+=(i&(-i))){
            data[i] = data[i] + v;
        }
    }

    T sum(int p){
        T res = init;
        for(int i=p;i>0;i-=(i&(-i))){
            res = res + data[i];
        }
        return res;
    }
};

vector<int> compressed(vector<int> line){
    map<int,int> m;
    foreach(i,line)m[i] = 0;
    int cnt = 0;
    foreach(i,m)i.second = cnt++;
    foreach(i,line)i = m[i];
    return line;
}

mint func(){
    int n = in();
    int k = in();
    vector<int> line(n);
    foreach(i,line)i=in();
    line = compressed(line);
    vector<char> ord(k);
    foreach(i,ord)i=in<char>();
    vector<mint> dp(n,1);
    foreach(o,ord){
        vector<mint> next(n,0);
        binary_indexed_tree<mint> bi(n+2);
        rep(i,n){
            mint add = 0;
            if(o=='<'){
                add = bi.sum(line[i]);
            }else{
                add = bi.sum(n+1) - bi.sum(line[i]+1);
            }
            next[i] = add;
            bi.add(line[i],dp[i]);
        }
        swap(dp,next);
    }
    mint res = 0;
    foreach(i,dp)res += i;
    return res;
}

int main(){
    println(func());
    return 0;
}

yukicoder

結果

テストケース

ソースコード