結果
問題 | No.1673 Lamps on a line |
ユーザー | kaiser l |
提出日時 | 2021-09-13 15:20:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 3,176 bytes |
コンパイル時間 | 7,201 ms |
コンパイル使用メモリ | 411,960 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-06-25 15:07:16 |
合計ジャッジ時間 | 9,384 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 73 ms
6,816 KB |
testcase_03 | AC | 74 ms
6,944 KB |
testcase_04 | AC | 128 ms
6,944 KB |
testcase_05 | AC | 9 ms
6,944 KB |
testcase_06 | AC | 108 ms
6,940 KB |
testcase_07 | AC | 92 ms
6,940 KB |
testcase_08 | AC | 5 ms
6,944 KB |
testcase_09 | AC | 132 ms
6,940 KB |
testcase_10 | AC | 140 ms
6,940 KB |
testcase_11 | AC | 15 ms
6,940 KB |
testcase_12 | AC | 150 ms
7,168 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/number.hpp> using namespace boost::multiprecision; using mint=modint1000000007; #define tpf typedef tpf double db;tpf long long ll; tpf string str;tpf vector<ll> vll; tpf vector<str> vs;tpf pair<ll,ll> pll; tpf vector<pll> vpll;tpf vector<vll> vvll; tpf cpp_int cp;tpf complex<db> com; tpf vector<bool> vb; int a,b; #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,n) #define F first #define S second #define psf push_front #define psb push_back #define epb emplace_back #define mkp make_pair #define All(x) x.begin(),x.end() #define Alld(x) All(x),greater<>() #define dupde(x) x.erase(unique(All(x)),x.end()) #define nxp next_permutation #define sep setprecision #define lob lower_bound const int mod = 1000000007;const ll INF=1e17; const db pi=acos(-1); const int di[]={-1,0,1,0}; const int dj[]={0,-1,0,1}; ll gcd(ll x,ll y){return y? gcd(y,x%y):x;} ll ncr(ll n,ll r){ ll x=1,y=1;rep(i,r){x*=(n-i);y*=(i+1);} return x/y; } mint modncr(ll n,ll r){ mint x=1,y=1;r=min(n-r,r); rep(i,r){x*=(n-i);y*=(i+1);} return x*y.inv(); } ll pncr(ll n,ll r){ vvll v(n+1,vll(n+1));v[0][0]=1; rep(i,n)rep(j,i+1){ v[i+1][j]+=v[i][j]; v[i+1][j+1]+=v[i][j]; } return v[n][r]; } template<class T> inline bool chmin(T& a, T b){ if(a>b){a=b;return true;}return false; } template<class T> inline bool chmax(T& a, T b){ if(a<b){a=b;return true;}return false; } ll to_base(ll n,ll i){ string s; while(n){s=to_string(n%i)+s;n/=i;} ll a=stoll(s);return a; } ll prime(ll n){ if(n==2)return 1; if(n%2==0||n==1)return 0; for(ll i=3;i*i<=n;i+=2)if(n%i==0)return 0; return 1; } vll divisor(ll n){ vll a; for(ll i=1;i*i<=n;i++){ if(n%i==0){ a.psb(i);if(i!=n/i)a.psb(n/i); } } sort(All(a));return a; } vector<pair<ll,ll>> prifac(ll n){ vector<pair<ll,ll>> a; for(ll i=2;i*i<=n;i++){ if(n%i!=0){continue;}ll exp=0; while(n%i==0){n/=i;exp++;} a.psb(pll(i,exp)); } if(n!=1){a.psb(pll(n,1));}return a; } vll cumsum(vll a){ ll sz=a.size(); vll dp(sz+1); rep(i,sz)dp[i+1]=dp[i]+a[i]; return dp; } vll eratos(ll n){ vll f(n+1),p; rep(i,n+1)f[i]=1; For(i,2,n+1){ if(f[i]){ for(ll j=2*i;j<=n;j+=i)f[j]=0; p.psb(i); } } return p; } vll eratos2(vll a,ll n){ vb x(n),ok(n,true);vll p,res; for(ll i:a)x[i]=true; For(i,2,n){ bool f=false; for(ll j=i;j<n;j+=i)if(x[j])f=true; if(f)p.psb(i); } for(ll i:p){ for(ll j=i;j<n;j+=i){ ok[j]=false; } } For(i,1,n)if(ok[i])res.psb(i); return res; } ll eulerf(ll n){ vll v(1);v[0]=n; vll res=eratos2(v,n+1); return res.size(); } ll eulerf2(ll n){ vpll a=prifac(n);ll res=n; for(auto i:a){res*=i.F-1;res/=i.F;} return res; } ll op(ll a,ll b){ return min(a,b); } ll e(){ return 1e9; } int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n,q,ans=0;cin>>n>>q; vll a(n); rep(i,q){ ll l,r;cin>>l>>r;l--; For(j,l,r){ if(a[j]==1){a[j]=0;ans--;} else {a[j]=1;ans++;} } cout<<ans<<endl; } return 0; }