If $$$k$$$ is greater or equal to $$$2$$$ you can always swap adjacent elements.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int arr[n];
        for(int i = 0;i < n;i++){
            cin>>arr[i];
        }
        if(is_sorted(arr,arr+n) || k > 1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    return 0;
}

Good

Mid

Bad

Think of each bit independently.

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int m[n][n];
        int arr[n];
        for(int i = 0;i < n;i++){
            arr[i] = (1<<30) - 1;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                cin>>m[i][j];
                if(i != j){
                    arr[i] &= m[i][j];
                    arr[j] &= m[i][j];
                }
            }
        }
        bool ok = true;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i != j && (arr[i] | arr[j]) != m[i][j]){
                    ok = false;
                }
            }
        }
        if(!ok){
            cout<<"NO\n";
        }
        else{
            cout<<"YES\n";
            for(int i = 0;i < n;i++){
                cout<<arr[i]<<" ";
            }
            cout<<"\n";
        }
    }
}

Good

Mid

Bad

Think of suffixes.

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];
        long long suf[n+1] = {0};
        for(int i = 0;i < n;i++){
            cin>>arr[i];
        }
        for(int i = n-1;i >= 0;i--){
            suf[i] = suf[i+1] + arr[i];
        }
        long long ans = suf[0];
        for(int i = 1;i < n;i++){
            if(suf[i] > 0){
                ans += suf[i];
            }
        }
        cout<<ans<<"\n";
    }
}

Good

Mid

Bad

Try using greedy to construct the answer bit by bit.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll T[LIM], P[LIM], n, k;
void solve() {
  rep(i, n) T[i]=P[i];
  ll ans=0;
  for(ll i=60; i>=0; --i) {
    ll sum=0;
    rep(j, n) {
      if(T[j]&(1ll<<i)) continue;
      ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
      p+=ans^(p&ans);
      sum+=p-T[j];
      if(sum > k){
          break;
      }
    }
    if(sum>k) continue;
    rep(j, n) {
      if(T[j]&(1ll<<i)) continue;
      ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
      p+=ans^(p&ans);
      T[j]=p;
    }
    ans+=1ll<<i;
    k-=sum;
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int q;
  cin >> n >> q;
  rep(i, n) cin >> P[i];
  while(q--) {
    cin >> k;
    solve();
  }
} 

Good

Mid

Bad

Try optimizing the greedy approach from $$$O$$$($$$n$$$) to $$$O$$$($$$1$$$).

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
ll dpsum[1<<20][20], dpcnt[1<<20], T[LIM];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll n, q;
  cin >> n >> q;
  ll sto=0, sfrom=0;
  rep(i, n) {
    cin >> T[i];
    sto+=(1ll<<20ll)-T[i];
    sfrom+=T[i];
    ++dpcnt[T[i]];
    ll sum=0;
    rep(j, 20) {
      sum+=T[i]&(1ll<<j);
      dpsum[T[i]][j]+=sum;
    }
  }
  rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) dpcnt[j]+=dpcnt[j+(1<<i)];
  rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) rep(l, 20) dpsum[j][l]+=dpsum[j+(1<<i)][l];
  while(q--) {
    ll k;
    cin >> k;
    if(k>=sto) {
      k+=sfrom;
      cout << k/n << '\n';
      continue;
    }
    ll ans=0;
    for(ll i=19; i>=0; --i) {
      ll x=(n-dpcnt[ans|(1<<i)])*(1ll<<i);
      x-=dpsum[ans][i]-dpsum[ans|(1<<i)][i];
      if(x<=k) {
        k-=x;
        ans|=1<<i;
      }
    }
    cout << ans << '\n';
  }
}
 

Good

Mid

Bad

Do mod $$$2$$$ in all coordinates and see how many different types of points you have in the end.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int sx,sy;
        cin>>sx>>sy;
        int x[n],y[n];
        set<int>p[2];
        for(int i = 0;i < n;i++){
            cin>>x[i]>>y[i];
            p[(x[i] % 2) ^ (y[i] % 2)].insert(i+1);
        }
        int v = (sx % 2) ^ (sy % 2);
        if(p[v].size() >= p[v^1].size()){
            cout<<"First"<<endl;
            v ^= 1;
            for(int i = 0;i < n;i++){
                if(i % 2 == 0){
                    int j;
                    if(!p[v].empty()){
                        j = (*p[v].begin());
                        p[v].erase(j);
                    }
                    else{
                        j = (*p[v^1].begin());
                        p[v^1].erase(j);
                    }
                    cout<<j<<endl;
                }
                else{
                    int j;
                    cin>>j;
                    if(p[0].count(j)){
                        p[0].erase(j);
                    }
                    else{
                        p[1].erase(j);
                    }
                }
            }
        }
        else{
            cout<<"Second"<<endl;
            for(int i = 0;i < n;i++){
                if(i % 2 == 1){
                    int j;
                    if(!p[v].empty()){
                        j = (*p[v].begin());
                        p[v].erase(j);
                    }
                    else{
                        j = (*p[v^1].begin());
                        p[v^1].erase(j);
                    }
                    cout<<j<<endl;
                }
                else{
                    int j;
                    cin>>j;
                    if(p[0].count(j)){
                        p[0].erase(j);
                    }
                    else{
                        p[1].erase(j);
                    }
                }
            }
        }
    }
}

Good

Mid

Bad

Use binary search the answer and 2-sat.

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ll> >adj,rev;
vector<ll>order;
vector<ll>vis,comp;
ll c;
ll cur;
ll val(ll idx,bool v){
    return cur + (2 * idx + v);
}
void dfs1(ll idx){
    vis[idx] = true;
    for(auto x:adj[idx]){
        if(!vis[x]){
            dfs1(x);
        }
    }
    order.pb(idx);
}
void dfs2(ll idx){
    comp[idx] = c;
    for(auto x:rev[idx]){
        if(!comp[x]){
            dfs2(x);
        }
    }
}
void build(ll s,ll e,ll idx){
    if(s == e){
        adj[idx].pb(val(s,0));
        rev[val(s,0)].pb(idx);
        return;
    }
    ll mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    adj[idx].pb(idx*2);
    adj[idx].pb(idx*2+1);
    rev[idx*2].pb(idx);
    rev[idx*2+1].pb(idx);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
    if(qs <= s && e <= qe){
        adj[val(k,1)].pb(idx);
        rev[idx].pb(val(k,1));
        return;
    }
    if(s > qe || qs > e){
        return;
    }
    ll mid = (s+e)/2;
    update(s,mid,qs,qe,idx*2,k);
    update(mid+1,e,qs,qe,idx*2+1,k);
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        ll u[m],v[m];
        f(i,0,m){
            cin>>u[i]>>v[i];
        }
        ll l = 1,r = n;
        ll ans = 1;
        cur = 4*n;
        while(l <= r){
            ll mid = (l+r)/2;
            order.clear();
            vis.assign(6*n+5,0);
            comp.assign(6*n+5,0);
            adj.assign(6*n+5,vector<ll>());
            rev.assign(6*n+5,vector<ll>());
            f(i,0,m){
                adj[val(u[i],0)].pb(val(v[i],1));
                adj[val(v[i],0)].pb(val(u[i],1));
                rev[val(u[i],1)].pb(val(v[i],0));
                rev[val(v[i],1)].pb(val(u[i],0));
            }
            build(1,n,1);
            f(k,1,n+1){
                ll l = max(1,k - mid + 1),r = k-1;
                update(1,n,l,r,1,k);
                l = k+1;
                r = min(n,k + mid - 1);
                update(1,n,l,r,1,k);
            }
            bool ok = true;
            c = 1;
            f(i,1,n+1){
                if(!vis[val(i,0)]){
                    dfs1(val(i,0));
                }
                if(!vis[val(i,1)]){
                    dfs1(val(i,1));
                }
            }
            reverse(order.begin(),order.end());
            for(auto x:order){
                if(!comp[x]){
                    dfs2(x);
                    c++;
                }
            }
            f(i,1,n+1){
                ok &= comp[val(i,0)] != comp[val(i,1)];
            }
            if(ok){
                l = mid + 1;
                ans = max(ans,mid);
            }
            else{
                r = mid - 1;
            }
        }
        cout<<ans<<"\n";
    }
}

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<basic_string<int>> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
template<int (*merge)(int,int), int (*init)(int)> struct DSU{
    vi sz, dat;
    DSU(int n) : sz(n,-1),dat(n) {
        for(int i=0;i<n;++i) dat[i] = init(i);
    }
    void link(int a, int b) {
        if(sz[a]>sz[b]) {
            swap(a,b);
        }
        sz[a]+=sz[b];
        sz[b]=a;
        dat[a] = merge(dat[a],dat[b]);
    }
    bool unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) link(pa,pb);
        return pa!=pb;
    }
    int get(int i) {
        return dat[find(i)];
    }
    int find(int a) {
        if(sz[a]<0) return a;
        return sz[a] = find(sz[a]);
    }
};
int dec(int i) {return i-1;}
int inc(int i) {return i+1;}
int mymin(int a, int b) {return min(a,b);}
int mymax(int a, int b) {return max(a,b);}
bool solve(const vvi& adj, const vvi& rev, int mid) {
    int n = rev.size()/2;

    DSU<mymin, dec> dsuL(n);
    DSU<mymax, inc> dsuR(n);
    auto getL = [&](int i) {
        if(i>=n) i-=n;
        int l = dsuL.get(i);
        if(l==-1 or abs(i-l)>=mid) return 0;
        return l+1;
    };
    auto getR = [&](int i) {
        if(i>=n) i-=n;
        int r = dsuR.get(i);
        if(r==n or abs(i-r)>=mid) return 0;
        return r+1;
    };
    auto rem = [&](int at) {
        if(at>=n) at-=n;
        if(at) dsuR.unite(at-1,at);
        if(at+1<n) dsuL.unite(at,at+1);
    };
    vector<bool> vis(n*2);
    vi ord;
    auto dfs = [&](auto&& self, int at) -> void {
        vis[at]=1;
        if(at<n) {
            while(int l = getL(at)) self(self,l-1+n);
            while(int r = getR(at)) self(self,r-1+n);
        } else rem(at);
        for(int to : adj[at]) if(!vis[to]) self(self,to);
        ord.push_back(at);

    };
    for(int i=0;i<2*n;++i) if(!vis[i]) dfs(dfs,i);
    reverse(all(ord));

    fill(all(vis),0);
    dsuL = DSU<mymin,dec>(n);
    dsuR = DSU<mymax,inc>(n);
    int comp=0;
    vi comps(2*n);
    auto dfs2 = [&](auto&& self, int at) -> void {
        comps[at]=comp;
        vis[at]=1;
        if(at>=n) {
            while(int l = getL(at)) self(self,l-1);
            while(int r = getR(at)) self(self,r-1);
        } else rem(at);
        for(int to : rev[at]) if(!vis[to]) self(self,to);

    };

    for(int i : ord) if(!vis[i]) {
        dfs2(dfs2,i);
        comp++;
    }
    for(int i=0;i<n;++i) if(comps[i]==comps[i+n]) return false;
    return true;


}
void solve() {
    int n,m; cin >> n >> m;
    vvi adj(2*n),rev(2*n);
    auto addE = [&](int u, int v) {
        adj[u].push_back(v);
        rev[v].push_back(u);
    };
    for(int i=0;i<m;++i) {
        int u,v; cin >> u >> v;
        --u,--v;
        addE(u+n,v);
        addE(v+n,u);
    }

    int lo=1,hi=n;
    while(lo<hi) {
        int mid = (lo+hi+1)/2;
        if(solve(adj,rev,mid)) {
            lo= mid;
        } else hi = mid-1;
    }
    cout << lo << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) solve();
}

Good

Mid

Bad

See how $$$n = 2$$$ case works.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<-n+1<<" "<<n<<endl;
    }
}

Think of the numbers in base $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        ll p = 1;
        ll ans = 0;
        f(j,0,31){
            if(k & (1<<j)){
                ans = (ans + p) % INF;
            }
            p *= n;
            p %= INF;
        }
        cout<<ans<<"\n";
    }
}

You need atmost 2 operations.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        char c;
        cin>>c;
        string s;
        cin>>s;
        vector<int>ans;
        bool ok = true;
        for(auto x:s){
            if(x != c){
                ok = false;
            }
        }
        if(!ok){
            f(i,1,n+1){
                ok = true;
                f(j,i,n+1){
                    ok &= (s[j-1] == c);
                    j += i-1;
                }
                if(ok){
                    ans.pb(i);
                    break;
                }
            }
            if(!ok){
                ans.pb(n);
                ans.pb(n-1);
            }
        }
        cout<<ans.size()<<"\n";
        for(auto x:ans){
            cout<<x<<" ";
        }
        cout<<"\n";
    }
}

Construct a graph from the comments.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ii> >adj;
int c[2];
int colour[700005];
bool ok;
int n;
void dfs(int idx){
    c[colour[idx]]+= (idx <= n);
    for(auto x:adj[idx]){
        if(colour[x.F] == -1){
            colour[x.F] = colour[idx] ^ x.S;
            dfs(x.F);
        }
        else if(colour[x.F] != (colour[idx] ^ x.S)){
            ///impossible
            ok = false;
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int m;
        cin>>n>>m;
        ///n original + m atmost fake nodes
        adj.assign(n+m+5,vector<ii>());
        f(i,0,n+m+5){
            colour[i] = -1;
        }
        int fake = n+1;
        f(i,0,m){
            int a,b;
            string c;
            cin>>a>>b>>c;
            if(c == "crewmate"){
                ///same team
                adj[a].pb(ii(fake,1));
                adj[fake].pb(ii(a,1));
                adj[fake].pb(ii(b,1));
                adj[b].pb(ii(fake,1));
                fake++;
            }
            else{
                ///different team
                adj[a].pb(ii(b,1));
                adj[b].pb(ii(a,1));
            }
        }
        int ans = 0;
        ok = true;
        f(i,1,n+1){
            if(colour[i] == -1){
                colour[i] = 0;
                c[0] = c[1] = 0;
                dfs(i);
                ans += max(c[0],c[1]);
            }
        }
        if(!ok){
            ans = -1;
        }
        cout<<ans<<"\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ii> >adj;
int c[2];
int colour[200005];
bool ok;
void dfs(int idx){
    c[colour[idx]]++;
    for(auto x:adj[idx]){
        if(colour[x.F] == -1){
            colour[x.F] = colour[idx] ^ x.S;
            dfs(x.F);
        }
        else if(colour[x.F] != (colour[idx] ^ x.S)){
            ///impossible
            ok = false;
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        adj.assign(n+5,vector<ii>());
        f(i,0,n+5){
            colour[i] = -1;
        }
        f(i,0,m){
            int a,b;
            string c;
            cin>>a>>b>>c;
            if(c == "crewmate"){
                ///same team
                adj[a].pb(ii(b,0));
                adj[b].pb(ii(a,0));
            }
            else{
                ///different team
                adj[a].pb(ii(b,1));
                adj[b].pb(ii(a,1));
            }
        }
        int ans = 0;
        ok = true;
        f(i,1,n+1){
            if(colour[i] == -1){
                colour[i] = 0;
                c[0] = c[1] = 0;
                dfs(i);
                ans += max(c[0],c[1]);
            }
        }
        if(!ok){
            ans = -1;
        }
        cout<<ans<<"\n";
    }
}

Think of how many colorings there are if you color only the root with one color.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
ll power(ll a,ll b,ll mod){
    if(b == 0){
        return 1;
    }
    ll ans = power(a,b/2,mod);
    ans *= ans;
    ans %= mod;
    if(b % 2){
        ans *= a;
    }
    return ans % mod;
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll k;
    cin>>k;
    ll othernodes = (1LL<<k) - 2;
    ll ans = power(4,othernodes,INF);
    ans *= 6;
    ans %= INF;
    cout<<ans<<"\n";
}

If you have a tree with a root with a fixed color and the others are all not predefined the number of colorings is $$$4^{nodes-1}$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
ll dp[(60 * 10000) + 5][6];
vll color[6];
vector<vector<int> >adj;
map<ll,int>label;
ll c[(60 * 10000) + 5];
ll solve(int i,int j){
    if(c[i] != -1 && c[i] != j){
        return 0;
    }
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    ll ans = 0;
    ll sum[2] = {0};
    for(auto x:color[j]){
        f(j,0,adj[i].size()){
            sum[j] += solve(adj[i][j],x);
            sum[j] %= INF;
        }
    }
    if(adj[i].empty()){
        sum[0] = sum[1] = 1;
    }
    if((ll)adj[i].size() == 1){
        sum[1] = 1;
    }
    ans = (sum[0] * sum[1]) % INF;
    return dp[i][j] = ans;
}
ll power(ll a,ll b,ll mod){
    if(b == 0){
        return 1;
    }
    ll ans = power(a,b/2,mod);
    ans *= ans;
    ans %= mod;
    if(b % 2){
        ans *= a;
    }
    return ans % mod;
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    color[0] = {1,2,4,5};
    color[1] = {0,2,3,5};
    color[2] = {0,1,3,4};
    color[3] = {1,2,4,5};
    color[4] = {0,2,3,5};
    color[5] = {0,1,3,4};
    map<string,ll>mp;
    mp["white"] = 0;
    mp["blue"] = 1;
    mp["red"] = 2;
    mp["yellow"] = 3;
    mp["green"] = 4;
    mp["orange"] = 5;
    memset(dp,-1,sizeof dp);
    memset(c,-1,sizeof c);
    ll k;
    cin>>k;
    ll n;
    cin>>n;
    ll posoi = (1LL<<k) - 1;
    int lab = 0;
    map<ll,int>ar;
    f(i,0,n){
        ll x;
        cin>>x;
        string s;
        cin>>s;
        ar[x] = mp[s];
        ll cur = x;
        while(cur >= 1 && !label.count(cur)){
            label[cur] = lab;
            lab++;
            posoi--;
            cur /= 2;
        }
    }
    adj.assign(lab + 5,vector<int>());
    for(auto x:label){
        if(ar.count(x.F)){
            c[x.S] = ar[x.F];
        }
        if(label.count(x.F * 2)){
            adj[x.S].pb(label[x.F * 2]);
        }
        if(label.count(x.F * 2 + 1)){
            adj[x.S].pb(label[x.F * 2 + 1]);
        }
    }
    ll ans = power(4,posoi,INF);
    ll sum = 0;
    f(j,0,6){
        sum += solve(label[1],j);
        sum %= INF;
    }
    ans *= sum;
    ans %= INF;
    cout<<ans<<"\n";
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ll n,k,s;
        cin>>s>>n>>k;
        if(s == k){
            cout<<"YES\n";
        }
        else if(k > s){
            cout<<"NO\n";
        }
        else{
            ll posa = s+k;
            ll l = s-k+1,r = s;
            ll siz = r - l + 1;
            ll a = 0,b = 0;
            ll num = (s / k) * k;
            b = r - num + 1;
            a = siz - b;
            if((s / k) % 2 == 1){
                posa -= b;
            }
            else{
                posa -= a;
            }
            if((2 * n + 1) > posa){
                cout<<"YES\n";
            }
            else{
                cout<<"NO\n";
            }
        }
    }
}